JUN TARUI
| Department of Computer and Network Engineering | Associate Professor |
| Cluster I (Informatics and Computer Engineering) | Associate Professor |
Researcher Information
Degree
Career
Research Activity Information
Paper
- Space-Efficient Algorithms for Longest Increasing Subsequence
M. Kiyomi; H. Ono; Y. Otachi; P. Schweitzer; J. Tarui
Proceedings of STACS2018: 35th International Symposium on Theoretical Aspects of Computer Science, 44:1-44:15, Mar. 2018, Peer-reviwed
International conference proceedings, English - Depth-First Search Using O(n) Bits
Tetsuo Asano; Taisuke Izumi; Masashi Kiyomi; Matsuo Konagaya; Hirotaka Ono; Yota Otachi; Pascal Schweitzer; Jun Tarui; Ryuhei Uehara
ALGORITHMS AND COMPUTATION, ISAAC 2014, 8889, 553-564, 2014, Peer-reviwed
International conference proceedings, English - Learning Boolean functions in AC(0) on attribute and classification noise-Estimating an upper bound on attribute and classification noise
Akinobu Miyata; Jun Tarui; Etsuji Tomita
THEORETICAL COMPUTER SCIENCE, 412, 35, 4650-4660, Aug. 2011, Peer-reviwed
Scientific journal, English - A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds
Kazuyuki Amano; Jun Tarui
THEORETICAL COMPUTER SCIENCE, 412, 18, 1646-1651, Apr. 2011, Peer-reviwed
Scientific journal, English - Smallest formulas for the parity of 2(k) variables are essentially unique
Jun Tarui
THEORETICAL COMPUTER SCIENCE, 411, 26-28, 2623-2627, Jun. 2010, Peer-reviwed
Scientific journal, English - Negation-Limited Complexity of Parity and Inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMICA, 54, 2, 256-267, Jun. 2009, Peer-reviwed
Scientific journal, English - Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences
H. Morizumi; J. Tarui
Theoretical Computer Science. DOI:10.1016/j.tcs.2008.10.030, 410, 11, 1054-1060, 2009, Peer-reviwed
Scientific journal, English - On the minimum number of completely 3-scrambling permutations
Jun Tarui
DISCRETE MATHEMATICS, 308, 8, 1350-1354, Apr. 2008, Peer-reviwed
Scientific journal, English - A well-mixed function with circuit complexity 5n +/- o(n): Tightness of the Lachish-Raz-type bounds
Kazuyuki Amano; Jun Tarui
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 4978, 342-+, 2008, Peer-reviwed
International conference proceedings, English - Smallest formulas for parity of 2(k) variables are essentially unique
Jun Tarui
COMPUTING AND COMBINATORICS, PROCEEDINGS, 5092, 92-99, 2008, Peer-reviwed
International conference proceedings, English - Reductions for Monotone Boolean Circuits
K. Iwama; H. Morizumi; J. Tarui
Theoretical Computer Science., 408, 208-212, 2008, Peer-reviwed
Scientific journal, English - Linear-size log-depth negation-limited inverter for k-tonic binary sequences
Hiroki Morizumi; Jun Tarui
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 4484, 605-+, 2007, Peer-reviwed
International conference proceedings, English - Finding a duplicate and a missing item in a stream
Jun Tarui
Theory and Applications of Models of Computation, Proceedings, 4484, 128-135, 2007
International conference proceedings, English - Negation-limited complexity of parity and inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 4288, 223-+, 2006, Peer-reviwed
International conference proceedings, English - On the Minimum Number of Completely 3-Scrambling Permutations
J. Tarui
Proc. of EuroComb05: European Conference on Combinatorics, Graph Theory and Applications, Discrete Mathematics & Theoretical Computer Science Conference Volume AE., 351-356, 2005, Peer-reviwed
International conference proceedings, English - Monotone Boolean Functions with s Zeros Farthest from Threshold Functions
K. Amano; J. Tarui
Proc. of EuroComb05: European Conference on Combinatorics, Graph Theory and Applications, Discrete Mathematics & Theoretical Computer Science Conference Volume AE., 11-16, 2005, Peer-reviwed
International conference proceedings, English - Constructing families of epsilon-approximate k-wise independent permutations
T Itoh; Y Takei; J Tarui
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E87A, 5, 993-1003, May 2004, Peer-reviwed
Scientific journal, English - Learning Boolean functions in AC(0) on attribute and classification noise
A Miyata; J Tarui; E Tomita
ALGORITHMIC LEARNING THEORY, PROCEEDINGS, 3244, 142-155, 2004
Scientific journal, English - On the negation-limited circuit complexity of merging
K Amano; A Maruoka; J Tarui
DISCRETE APPLIED MATHEMATICS, 126, 1, 3-8, Mar. 2003, Peer-reviwed
Scientific journal, English - On the Sample Size of k-restricted Min-Wise Independent Permutations and Other k-Wise Distributions
T. Itoh; Y. Takei; J. Tarui
STOC03: Proc. of the 35th Annual ACM Symposium on Theory of Computing, ACM Press. DOI: 10.1145/780542.780645, Network Operation Center,Tokyo Institute of Technology, 3, 1, 710-719, 2003, Peer-reviwed
International conference proceedings, English - A nearly linear size 4-min-wise independent permutation family by finite geometries
J Tarui; T Itoh; Y Takei
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION, 2764, 396-408, 2003
Scientific journal, English - On permutations with limited independence
T Itoh; Y Takei; J Tarui
PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 137-146, 2000, Peer-reviwed
International conference proceedings, English - On complexity of computing the permanent of a rectangular matrix
T Kawabata; J Tarui
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E82A, 5, 741-744, May 1999, Peer-reviwed
Scientific journal, English - Learning DNF by approximating inclusion-exclusion formulae
J Tarui; T Tsukiji
FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 215-220, 1999, Peer-reviwed
International conference proceedings, English - On the Negation-Limited Circuit Complexity of Merging
K. Amano; A. Maruoka; J. Tarui
Lecture Notes in Computer Science vol. 1627: Proc. of COCOON99: The 5th Annual International Computing and Combinatorics Conference, Springer., 204-209, 1999
International conference proceedings, English - Some observations on the computational complexity of graph accessibility problem
Jun Tarui; Seinosuke Toda
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 1627, 18-30, 1999, Peer-reviwed
International conference proceedings, English - Finding relevant variables in PAC model with membership queries
D Guijarro; J Tarui; T Tsukiji
ALGORITHMIC LEARNING THEORY, PROCEEDINGS, 1720, 313-322, 1999, Peer-reviwed
Scientific journal, English - The asymptotic complexity of merging networks
PB Miltersen; M Paterson; J Tarui
JOURNAL OF THE ACM, 43, 1, 147-165, Jan. 1996, Peer-reviwed
Scientific journal, English - On ACC
Richard Beigel; Jun Tarui
Computational Complexity, Birkhäuser-Verlag, 4, 4, 350-366, Dec. 1994, Peer-reviwed
Scientific journal, English - PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIAL-TIME HIERARCHY
J TARUI
THEORETICAL COMPUTER SCIENCE, 113, 1, 167-183, May 1993, Peer-reviwed
Scientific journal, English - Computing Symmetric Functions with AND/OR Circuits and a Single Majority Gate
Z. Zhang; D. Barrington; J. Tarui
Lecture Notes in Computer Science vol. 665: Proc. of STACS93: The 10th Annual Symposium on Theoretical Aspects of Computer Science, Springer. DOI: 10.1007/3-540-56503_53, 535-554, 1993, Peer-reviwed
International conference proceedings, English - ON PROBABILISTIC ACC CIRCUITS WITH AN EXACT-THRESHOLD OUTPUT GATE
R BEIGEL; J TARUI; S TODA
ALGORITHMS AND COMPUTATION, 650, 420-429, 1992, Peer-reviwed
International conference proceedings, English - ON PROBABILISTIC ACC CIRCUITS WITH AN EXACT-THRESHOLD OUTPUT GATE
R BEIGEL; J TARUI; S TODA
LECTURE NOTES IN COMPUTER SCIENCE, 650, 420-429, 1992, Peer-reviwed
Scientific journal, English - THE ASYMPTOTIC COMPLEXITY OF MERGING NETWORKS
PB MILTERSEN; M PATERSON; TR JUN
33RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE : PROCEEDINGS, 236-246, 1992, Peer-reviwed
International conference proceedings, English - DEGREE COMPLEXITY OF BOOLEAN FUNCTIONS AND ITS APPLICATIONS TO RELATIVIZED SEPARATIONS
J TARUI
PROCEEDINGS OF THE SIXTH ANNUAL STRUCTURE IN COMPLEXITY THEORY CONFERENCE, 382-390, 1991, Peer-reviwed
International conference proceedings, English - ON ACC
R BEIGEL; J TARUI
PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 783-792, 1991, Peer-reviwed
International conference proceedings, English - RANDOMIZED POLYNOMIALS, THRESHOLD CIRCUITS, AND THE POLYNOMIAL HIERARCHY
J TARUI
LECTURE NOTES IN COMPUTER SCIENCE, 480, 238-250, 1991, Peer-reviwed
Scientific journal, English
MISC
- ［京都賞業績紹介］A.C.ヤオ／通信計算量理論：ヤオの卓越した独創の産物
垂井淳
Jan. 2022, 数学セミナー2022年１月号 https://amzn.to/3v13ibP, 20-25, Japanese, Invited, Introduction commerce magazine - Google Scholar Profile: http://scholar.google.co.jp/citations?user=7hrsV9cAAAAJ
Jun Tarui
2018, 0-0, English, Others - P≠NP予想，代数的計算量
垂井淳
日本評論社, Dec. 2013, 数学セミナー2013年12月号：P≠NP予想特集号, 52, 12, 18-22, Japanese, Introduction other, 0386-4960, 40019861947, AN10333470 - Theory and Applications of Models of Computation 2011 Preface
Mitusnori Ogihara; Jun Tarui
Sep. 2013, THEORETICAL COMPUTER SCIENCE, 505, 1-1, English, Others, 0304-3975, 1879-2294, WOS:000325905200001 - エキスパンダーとランダムネスの節約・除去
垂井淳
サイエンス社, 2006, 数理科学2006年9月号：特集「ランダムネス」，2006., 44, 9, 31-36, Japanese, Introduction other, 0386-2240, 40007375217, AN00125207 - Recent Progress on Min-Wise Independent Permutations
T. Itoh; Y. Takei; J. Tarui
The notion of "a family of min-wise independent permutations" was introduced by Broder, et al. It is a basic tool to estimate resemblance between documents and has applications of detecting almost identical documents on the Web and of reducing the amount of randomness used by algorithms. In this paper, we focus on min-wise independent permutations and the related notions, e. g., ε-approximate min-wise independent permutations, k-restricted min-wise independent permutatios, etc., and overview the recen tresults on (1) how to estimate resemblance between documents by min-wise independent permutations ; (2) upper and lower bounds for the size of min-wise independent permutations ; (3) upper and lower bounds for the size of ε-approximate min-wise independent permutations ; (4) upper and loer obunds for the size of k-restricted min-wise independent permutations., The Institute of Electronics, Information and Communication Engineers, 2003, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-49, 2003., 103, 394, 41-50, English, Introduction other, 0913-5685, 110003178798, AN10013152
Books and other publications
Lectures, oral presentations, etc.
- Expanders and Computational Complexity Theory
Jun TARUI
Invited oral presentation, エクスパンダーグラフの新しい構成手法の確立とその応用2
05 Sep. 2023
04 Sep. 2023- 08 Sep. 2023 - ブログは研究に役立つか？どのように？
垂井淳
Invited oral presentation, Japanese, 国際学術情報流通基盤整備事業(SPARC Japan)2015年第3回セミナー招待講演（会場：国立情報学研究所）, Invited, 国際学術情報流通基盤整備事業(SPARC Japan), 国立情報学研究所（NII), Domestic conference
19 Jan. 2016 - 計算量理論のいろんな話題
垂井淳
Invited oral presentation, Japanese, 計算量理論秋学校講演(熱海, 9月24日--26日, 2012), 計算量理論秋学校講演(熱海, 9月24日--26日, 2012)
Sep. 2012 - 計算の複雑さと証明の複雑さ
垂井淳
Invited oral presentation, Japanese, 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012), 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012)
Sep. 2012 - Complexity of Finding a Duplicate in a Stream
Jun Tarui
Invited oral presentation, English, NII Shonan Meeting: "Large-Scale Distributed Computation", NII Shonan Meeting: "Large-Scale Distributed Computation", (Zushi, Japan, Jan 12--15, 2012), International conference
Jan. 2012 - DeolalikarのP≠NP論文をめぐって
垂井淳
Invited oral presentation, Japanese, 電子情報通信学会，コンピュテーション研究会，p.47，信学技報COMP2010-38, 2010.
2010 - Negation-Limited Complexity of Parity and Inverters
森住大樹; 垂井淳; 岩間一雄
Oral presentation, Japanese, 2007冬のLAシンポジウム，京都大学数理解析研究所講究録 no. 1554, 131--138, 2007.
2007 - 回路計算量の5nの下界に対する5nの上界
天野一幸; 垂井淳
Oral presentation, Japanese, 2007年夏のLAシンポジウム，2007.
2007 - Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic 0/1 Sequences
H. Morizumi; J. Tarui
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報COMP2006-49, 57--60, 2006.
2006 - Explicit Construction of k-Wise Nearly Random Permutations by Iterated Feistel Transform
T. Itoh; T. Nagatani; J. Tarui
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報COMP2004-7, 2004.
2004 - あるノイズモデルにおけるブール関数学習について
宮田明信; 垂井淳; 富田悦次
Oral presentation, Japanese, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-70, pp. 9--16, 2003.
2003 - A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries
J. Tarui; T. Itoh; Y. Takei
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-21, pp. 35-42, 2003.
2003 - On the Sample Size of k-Min-Wise Independent Permutations and Other k-Wise Distributions
T. Itoh; Y. Takei; J. Tarui
Oral presentation, English, 電子情報通信学会コンピュテーション研究会，信学技報COMP2002-33, pp. 25-32, 2002.
2002 - ブール関数のsensitivity, block sensitivity, certificate complexityについて
天羽健策; 垂井淳
Oral presentation, Japanese, 電子情報通信学会コンピュテーション研究会，信学技報COMP97-118, 1998.
1998
Courses
- 情報数理工学実験第二Ａ・Ｂ
The University of Electro-Communications - 情報数理工学実験第二Ａ・Ｂ
電気通信大学 - Advanced Communication Engineering and Informatics IV (Computational Complexity)
The University of Electro-Communications - Advanced Communication Engineering and Informatics IV (Computational Complexity)
電気通信大学 - Mathematical Information Science Laboratory ⅡB
The University of Electro-Communications - 情報数理工学実験第二B
電気通信大学 - Advanced Study for Theoretical Computer Science
The University of Electro-Communications - Theory of Computing
The University of Electro-Communications - Advanced Communication Engineering and Informatics Ⅲ（Computational Complexity）
The University of Electro-Communications - Advanced Communication Engineering and Informatics Ⅲ（Computational Complexity）（学域）
電気通信大学 - 理論計算機科学特論
The University of Electro-Communications - 計算理論
The University of Electro-Communications - Computational Complexity
電気通信大学 - 離散数学
The University of Electro-Communications - 離散数学
電気通信大学 - 理論計算機科学特論
The University of Electro-Communications - 理論計算機科学特論
電気通信大学 - 計算理論
The University of Electro-Communications - 計算理論
電気通信大学 - Computational Complexity
The University of Electro-Communications - Computational Complexity
The University of Electro-Communications
Research Themes
- Exploring the Limits of Computation in the Scenario of Constrained Work Space
Asano Tetsuo; Guenter Rote; Wolfgang Mulzer; Ovidiu Daescu
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Japan Advanced Institute of Science and Technology, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), In this research we have developed powerful techniques for analysis toward establishment of nontrivial lower and upper bounds on the constrained work space. The most fundamental problem is to seek for each entry in a given array of real numbers one of nearest greater values. Using linear size of work space we can design a linear time algorithm for solving the problem. Our problem is whether we can solve the problem in an efficient way using less work space. In this research we showed that we have an efficient algorithm using only constant amount of work space. We also had results on time and space tradeoffs on the problem. We obtained other many results in basic problems in computational geometry and graph theory., 24106004
28 Jun. 2012 - 31 Mar. 2017 - Study of Circuit Complexity Using Polynomial Representations of Boolean Functions
Tarui Jun
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), We have shown that for an undirected graph with n vertices and m edges, Depth-First Search (DFS) is possible using n+o(n) bits of memory. For a directed acyclic graph, DFS is possible using n/[exp(Omega(root(log n))) ] bits of memory. We have also obtained similar results for several other graph problems. Recently, researchers are finding more and more interesting connections between Exponential-Time Hypothesis (ETH) and the time complexity of polynomial-time solvable problems. For example, it is now known that ETH implies that a truly sub-cubic algorithm does *not* exist for a certain graph problem. Our results above seem to suggest that we should investigate space-complexity analogues of this phenomena: What are the consequences of the conjecture "Problem A requires linear space" ?, 25330010
01 Apr. 2013 - 31 Mar. 2016 - Propositional Proof Complexity: Analysis fromComputational Complexity Perspectives
TARUI Jun
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), We have obtained a new result about proof complexity of the pigeonhole principle by analyzing the space complexity and the communication complexity of findig a duplicate in a stream. Our new proof method is interesting in its own. For circuit complexity, which is closely related to proof complexity, we have (1) extended a noise-tolerant learning algorithm for AC0 functions, (2) have identified a concrete barrier for provindg a circuit-size lower bound bigger than 5n, and (3) have shown that, for n a power of 2, a smallest DeMorgan formula computing Parity of n Boolean variables is essentially unique., 22500012
2010 - 2012 - Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications
TOMITA Etsuji; TAKAHASHI Haruhisa; NISHINO Tetsuro; WAKATSUKI Mitsuo; TARUI Jun
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), 最大クリークを抽出する新しいアルゴリズムMCSを開発し,格段に高速であることを明らかにした.これにより,従来では100日以上かかっても解けなかった幾つかの問題を100秒以内で解くことに成功した.最大クリーク問題が多項式時間的に可解となる基本的結果も確立した.また,最大クリーク抽出アルゴリズムがハイパーグラフにおいても効率的に稼働する様に拡張した.更に,これらのアルゴリズムをデータマイニングなどの実問題に応用して有効な結果を得た., 19500010
2007 - 2009 - 量子論理回路の最適化に関する研究
西野 哲朗; 垂井 淳; 太田 和夫; 國廣 昇
日本学術振興会, 科学研究費助成事業, 電気通信大学, 特定領域研究, 量子コンピュータの物理的実現には、多くの困難が存在する。例えば、量子もつれ合いを保つことができる時間が短いことや、複雑な量子操作を行なうことが難しいこと等が挙げられる。これらの問題の解決において、量子回路のサイズは非常に重要である。本研究では、量子回路サイズの新たな評価方法について検討する。特に、C-NOTゲートに着目し、量子回路計算量とC-NOTゲート数の関係について、幾つかの定理を示した。 現在、量子コンピュータの物理的実現について盛んに研究が行われているが、その実現には多くの困難が伴う。そのうちの一つとして、量子コンピュータは量子重ね合わせ状態という量子力学的にデリケートな状態を取ることが挙げられる。そのため、サイズの大きな量子コンピュータの複雑な量子重ね合わせ状態を長時間維持することは非常に困難となる それに加えて、量子コンピュータは扱えるビット数が大きくなるほど実現が困難となる。すなわち、同じアルゴリズムを実行する場合、量子コンピュータにおいては、特に、時間計算量および領域計算量を縮小することが本質的に重要な問題となる。そこで、本研究では、量子回路のゲート数とビット数の関係についても考察した。具体的には、あるアルゴリズムを実行する量子回路に対して、それに補助量子ビットを付加し、回路を再構成することで、ゲートの総数をさらに縮小できるかどうかを検証した。 我々は古典コンピュータを用いてアルゴリズムを実行するときに、計算時間の短縮のために、計算の途中で、その計算結果の一部をメモリの別の場所に一時的に保管することをよく行う。量子コンピュータの回路設計においても、補助量子ビットはそのようなワークビットとしてたびたび用いられるが、そこで使われる補助量子ビットは厳密に定義されているわけではない。本研究では、どのような種類の補助量子ビットにゲート数縮小の効果があるのかを検証するために、補助量子ビットの分類と定式化を行った。, 16092208
2004 - 2007 - 計算量の理論-下界の証明・計算量の正確な決定・最適アルゴリズムの一意性の問題
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 今年度得られた結果のいくつかを以下の簡潔に述べる。 1. 否定数限定回路でのmergingのcomplexityをかなり正確に決定することに成功した:2つの長さnのソートされた0,1列をマージするa個のNOT gateとAND,OR gateよりなる最小の回路のサイズは、a【less than or equal】log_2nのときΘ(nlog_2n/2^a)であることを示すことができた。 2. DNF式にたいして効率的PAC(Probably Approximately Correct)学習が可能かどうかという問題は、計算論学習理論における最重要な未解決問題のひとつである。この問題についてのあるアプローチの可能性と限界にてついての結果を得た:長さがmのmonomialで、ターゲットであるDNF式との相関があるものを弱学習することとboostingよってDNF式の学習を達成しようとするとき、mがn^<1/2>より小さい場合は、弱学習が不可能であり、n^<1/2>くらいまで大きくとると可能であることを示した。 3. Broder他がSTOC98で発表したMIn-wise independent permutation familyについて、その仕事で未解決問題として残されていたもののいくつかにたいしてそのようなfamily sizeにたいして上界・下界を示すことができた。 4. m by n rectangular matrix(m【less than or equal】n)のPermanentをO(n2^m+3^m)arithmetic operationsによって計算するアルゴリズムを与えた。, 09780257
1997 - 1998 - 組合せ論的計算量の理論-特に下界の証明と最適アルゴリズムの-意性の問題
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 本研究では、いくつかの組合せ論的計算モデルについて、計算能力の解析と“自然な"計算問題を解くのに必要な計算資源の量の分析を行なった。以下では、今年度論文としてまとめるに至ったものについてより詳しく述べる。 1.constant-depth polynomial-sizeの組合せ論理回路によって定義される計算量のクラスACCについて、以前よりRichard Beigel(Yale大学)と共同研究を行なっていたが、今年度 この結果をJ.of Comp.Complexityに発表した。この論文では、クラスACCに属する任意のブール関数は、深さ2のある形の回路で計算可能であること等が示されている。 2.整列されている2つのリストをcomparator(比較器)によって併合するmergng networkに必要なcomparatorの数について、Batcherのodd-even mergeに基づくものが、漸近的に最適であるという結果を含む論文のjournal versionを今年度まとめた。これは、以前よりの共同研究を発展させたもので、論文は現在審査中である。, 06780246
1994 - 1995 - Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems
TOMITA Etsuji; WAKATSUKI Mitsuo; TARUI Jun; TAKAHASHI Haruhisa
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for General Scientific Research (C), We have developed a simple and branch and bound algorithm for finding a maximum clique of a graph. Our approach successively applies a pruning method based on greedy coloring followed by suitable arrangements for the vertices in consideration. The algorithm reduces the number of search tree nodes very effectively and hence runs fast. It is experimentally confirmed to run faster for a number of random graphs with up to 600 vertices and other graphs than several algorithms which have been appeared in the literature. This algorithm has been further improved by combining several methods. We have also developed a simple branch and bound algorithm for finding a maximum weight clique in a weighted graph. Its bounding rule is principally based upon a sequentail approximate coloring which has been applied in the above algorithms. Based upon Boltzmann machines, a new algorithm is given for approximately coloring a graph. Besides, the above algorithm for finding a maximum weight clique is applied for an RNA secondary structure prediction problem., 06680311
1994 - 1995
