垂井 淳
| 情報・ネットワーク工学専攻 | 准教授 |
| Ⅰ類（情報系） | 准教授 |
研究者情報
学位
経歴
研究活動情報
論文
- 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, 出版日 2018年03月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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, 出版日 2011年08月, 査読付
研究論文（学術雑誌）, 英語 - 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, 出版日 2011年04月, 査読付
研究論文（学術雑誌）, 英語 - Smallest formulas for the parity of 2(k) variables are essentially unique
Jun Tarui
THEORETICAL COMPUTER SCIENCE, 411巻, 26-28号, 掲載ページ 2623-2627, 出版日 2010年06月, 査読付
研究論文（学術雑誌）, 英語 - Negation-Limited Complexity of Parity and Inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMICA, 54巻, 2号, 掲載ページ 256-267, 出版日 2009年06月, 査読付
研究論文（学術雑誌）, 英語 - 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年, 査読付
研究論文（学術雑誌）, 英語 - On the minimum number of completely 3-scrambling permutations
Jun Tarui
DISCRETE MATHEMATICS, 308巻, 8号, 掲載ページ 1350-1354, 出版日 2008年04月, 査読付
研究論文（学術雑誌）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Smallest formulas for parity of 2(k) variables are essentially unique
Jun Tarui
COMPUTING AND COMBINATORICS, PROCEEDINGS, 5092巻, 掲載ページ 92-99, 出版日 2008年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Reductions for Monotone Boolean Circuits
K. Iwama; H. Morizumi; J. Tarui
Theoretical Computer Science., 408巻, 掲載ページ 208-212, 出版日 2008年, 査読付
研究論文（学術雑誌）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Finding a duplicate and a missing item in a stream
Jun Tarui
Theory and Applications of Models of Computation, Proceedings, 4484巻, 掲載ページ 128-135, 出版日 2007年
研究論文（国際会議プロシーディングス）, 英語 - Negation-limited complexity of parity and inverters
Kazuo Iwama; Hiroki Morizumi; Jun Tarui
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 4288巻, 掲載ページ 223-+, 出版日 2006年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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, 出版日 2004年05月, 査読付
研究論文（学術雑誌）, 英語 - 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年
研究論文（学術雑誌）, 英語 - On the negation-limited circuit complexity of merging
K Amano; A Maruoka; J Tarui
DISCRETE APPLIED MATHEMATICS, 126巻, 1号, 掲載ページ 3-8, 出版日 2003年03月, 査読付
研究論文（学術雑誌）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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年
研究論文（学術雑誌）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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, 出版日 1999年05月, 査読付
研究論文（学術雑誌）, 英語 - Learning DNF by approximating inclusion-exclusion formulae
J Tarui; T Tsukiji
FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 掲載ページ 215-220, 出版日 1999年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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年
研究論文（国際会議プロシーディングス）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Finding relevant variables in PAC model with membership queries
D Guijarro; J Tarui; T Tsukiji
ALGORITHMIC LEARNING THEORY, PROCEEDINGS, 1720巻, 掲載ページ 313-322, 出版日 1999年, 査読付
研究論文（学術雑誌）, 英語 - The asymptotic complexity of merging networks
PB Miltersen; M Paterson; J Tarui
JOURNAL OF THE ACM, 43巻, 1号, 掲載ページ 147-165, 出版日 1996年01月, 査読付
研究論文（学術雑誌）, 英語 - On ACC
Richard Beigel; Jun Tarui
Computational Complexity, Birkhäuser-Verlag, 4巻, 4号, 掲載ページ 350-366, 出版日 1994年12月, 査読付
研究論文（学術雑誌）, 英語 - PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIAL-TIME HIERARCHY
J TARUI
THEORETICAL COMPUTER SCIENCE, 113巻, 1号, 掲載ページ 167-183, 出版日 1993年05月, 査読付
研究論文（学術雑誌）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - ON PROBABILISTIC ACC CIRCUITS WITH AN EXACT-THRESHOLD OUTPUT GATE
R BEIGEL; J TARUI; S TODA
ALGORITHMS AND COMPUTATION, 650巻, 掲載ページ 420-429, 出版日 1992年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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年, 査読付
研究論文（学術雑誌）, 英語 - THE ASYMPTOTIC COMPLEXITY OF MERGING NETWORKS
PB MILTERSEN; M PATERSON; TR JUN
33RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE : PROCEEDINGS, 掲載ページ 236-246, 出版日 1992年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 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年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - ON ACC
R BEIGEL; J TARUI
PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 掲載ページ 783-792, 出版日 1991年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - RANDOMIZED POLYNOMIALS, THRESHOLD CIRCUITS, AND THE POLYNOMIAL HIERARCHY
J TARUI
LECTURE NOTES IN COMPUTER SCIENCE, 480巻, 掲載ページ 238-250, 出版日 1991年, 査読付
研究論文（学術雑誌）, 英語
MISC
- ［京都賞業績紹介］A.C.ヤオ／通信計算量理論：ヤオの卓越した独創の産物
垂井淳
出版日 2022年01月, 数学セミナー2022年１月号 https://amzn.to/3v13ibP, 掲載ページ 20-25, 日本語, 招待, 記事・総説・解説・論説等（商業誌、新聞、ウェブメディア） - Google Scholar Profile: http://scholar.google.co.jp/citations?user=7hrsV9cAAAAJ
Jun Tarui
出版日 2018年, 掲載ページ 0-0, 英語, その他 - P≠NP予想，代数的計算量
垂井淳
日本評論社, 出版日 2013年12月, 数学セミナー2013年12月号：P≠NP予想特集号, 52巻, 12号, 掲載ページ 18-22, 日本語, 記事・総説・解説・論説等（その他）, 0386-4960, 40019861947, AN10333470 - Theory and Applications of Models of Computation 2011 Preface
Mitusnori Ogihara; Jun Tarui
出版日 2013年09月, THEORETICAL COMPUTER SCIENCE, 505巻, 掲載ページ 1-1, 英語, その他, 0304-3975, 1879-2294, WOS:000325905200001 - エキスパンダーとランダムネスの節約・除去
垂井淳
サイエンス社, 出版日 2006年, 数理科学2006年9月号：特集「ランダムネス」，2006., 44巻, 9号, 掲載ページ 31-36, 日本語, 記事・総説・解説・論説等（その他）, 0386-2240, 40007375217, AN00125207 - Recent Progress on Min-Wise Independent Permutations
T. Itoh; Y. Takei; J. Tarui
Broderらによって提案された"最小値独立置換族"は,電子文書の類似度を効率的に判定する際の基本的な概念であり,WEB上の類似文書の検出・確率的アルゴリズムの効率化などの応用を持つことが知られている.本稿では,最小値独立置換族(及びその拡張概念であるε-近似的最小中国財務局長独立置換族・k-制限最小値独立置換族など)に関する最近の成果-(1)最小値独立置換族を用いた電子文書の類似性判定法 : (2)最小値独立置換族のサイズに関する上界と下界 ; (3)ε-近似的最初値独立置換族のサイズに関する上界と下界 ; (4)k-制限最小値独立置換族のサイズに関する上界と下界-について述べ,最小値独立置換族(及びその拡張概念)の構成方法の現状を概観する., 一般社団法人電子情報通信学会, 出版日 2003年, 電子情報通信学会コンピュテーション研究会，信学技報COMP2003-49, 2003., 103巻, 394号, 掲載ページ 41-50, 英語, 記事・総説・解説・論説等（その他）, 0913-5685, 110003178798, AN10013152
書籍等出版物
講演・口頭発表等
- エクスパンダーと計算量理論
Jun TARUI
口頭発表（招待・特別）, エクスパンダーグラフの新しい構成手法の確立とその応用2
発表日 2023年09月05日
開催期間 2023年09月04日- 2023年09月08日 - ブログは研究に役立つか？どのように？
垂井淳
口頭発表（招待・特別）, 日本語, 国際学術情報流通基盤整備事業(SPARC Japan)2015年第3回セミナー招待講演（会場：国立情報学研究所）, 招待, 国際学術情報流通基盤整備事業(SPARC Japan), 国立情報学研究所（NII), 国内会議
発表日 2016年01月19日 - 計算量理論のいろんな話題
垂井淳
口頭発表（招待・特別）, 日本語, 計算量理論秋学校講演(熱海, 9月24日--26日, 2012), 計算量理論秋学校講演(熱海, 9月24日--26日, 2012)
発表日 2012年09月 - 計算の複雑さと証明の複雑さ
垂井淳
口頭発表（招待・特別）, 日本語, 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012), 京大数理解析研究所研究集会「証明論と複雑性」(9月12日--14日, 2012)
発表日 2012年09月 - Complexity of Finding a Duplicate in a Stream
Jun Tarui
口頭発表（招待・特別）, 英語, NII Shonan Meeting: "Large-Scale Distributed Computation", NII Shonan Meeting: "Large-Scale Distributed Computation", (Zushi, Japan, Jan 12--15, 2012), 国際会議
発表日 2012年01月 - DeolalikarのP≠NP論文をめぐって
垂井淳
口頭発表（招待・特別）, 日本語, 電子情報通信学会，コンピュテーション研究会，p.47，信学技報COMP2010-38, 2010.
発表日 2010年 - Negation-Limited Complexity of Parity and Inverters
森住大樹; 垂井淳; 岩間一雄
口頭発表（一般）, 日本語, 2007冬のLAシンポジウム，京都大学数理解析研究所講究録 no. 1554, 131--138, 2007.
発表日 2007年 - 回路計算量の5nの下界に対する5nの上界
天野一幸; 垂井淳
口頭発表（一般）, 日本語, 2007年夏のLAシンポジウム，2007.
発表日 2007年 - Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic 0/1 Sequences
H. Morizumi; J. Tarui
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2006-49, 57--60, 2006.
発表日 2006年 - Explicit Construction of k-Wise Nearly Random Permutations by Iterated Feistel Transform
T. Itoh; T. Nagatani; J. Tarui
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2004-7, 2004.
発表日 2004年 - あるノイズモデルにおけるブール関数学習について
宮田明信; 垂井淳; 富田悦次
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会，信学技報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
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報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
口頭発表（一般）, 英語, 電子情報通信学会コンピュテーション研究会，信学技報COMP2002-33, pp. 25-32, 2002.
発表日 2002年 - ブール関数のsensitivity, block sensitivity, certificate complexityについて
天羽健策; 垂井淳
口頭発表（一般）, 日本語, 電子情報通信学会コンピュテーション研究会，信学技報COMP97-118, 1998.
発表日 1998年
担当経験のある科目_授業
- 情報数理工学実験第二Ａ・Ｂ
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 - Computational Complexity
電気通信大学 - 離散数学
電気通信大学 - 離散数学
電気通信大学 - 理論計算機科学特論
The University of Electro-Communications - 理論計算機科学特論
電気通信大学 - 計算理論
電気通信大学 - 計算理論
電気通信大学 - Computational Complexity
The University of Electro-Communications - Computational Complexity
電気通信大学
共同研究・競争的資金等の研究課題
- 記憶領域制限シナリオにおける計算限界の解明
浅野 哲夫; 上原 隆平; 垂井 淳; 小野 廣隆; 清見 礼; 大舘 陽太
日本学術振興会, 科学研究費助成事業, 北陸先端科学技術大学院大学, 新学術領域研究(研究領域提案型), 本研究では，対数領域計算モデルでの非自明な下界と上界の確立に向けて強力な解析技法の開発を行った．与えられた実数値配列上で，各要素の対して，より大きな値をもつ要素の中で直近のものを見つける直近上位要素発見問題を基本問題として考えた．線形の作業領域を許すと線形時間ですべての直近上位要素を求めることができるが，少ない作業領域でどの程度の高速化が達成できるかが問題である．本研究では，定数個のメモリを用いるだけで十分に高速なアルゴリズムを開発することに成功し，その計算時間とメモリ量との間のトレードオフについても成果を得た．同様の研究結果を計算幾何学やグラフ理論の基本的な問題についても得ることができた．, 24106004
研究期間 2012年06月28日 - 2017年03月31日 - ブール関数の多項式表現を用いた回路計算量の解析
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), n個の頂点とm本の辺をもつ無向グラフに対して，n+o(n)ビットの記憶領域だけを用いて深さ優先探索が可能であり，有向非巡回グラフの場合は，n/[exp(Omega(root(log n)))]ビットの記憶容量だけを用いて深さ優先探索が可能であることがわかった．深さ優先探索以外の複数の問題についても同様の結果を得た．指数時間予想と「この問題をnの3乗より早くは解けない」といった予想の関連性が最近明らかになりつつあるが，我々の結果は，「記憶領域量がnの(1-epsilon)乗しかない場合は計算は不可能」といった予想と他の問題の領域計算量との関係解明の重要性を示唆している点が特に興味深い．, 25330010
研究期間 2013年04月01日 - 2016年03月31日 - 命題論理の証明の複雑さに関する計算量理論からの解析
垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 鳩ノ巣原理の証明複雑さに関して,ストリーム計算における重複要素発見問題の領域計算量および通信計算量の解析を応用して新結果を得ることに成功した。開発し用いた手法はさらなる応用が期待できる。証明の複雑さと密接に関連する回路計算量に関して,ノイズ下でのAC0関数の学習アルゴリズムの拡張,5nより大きい回路サイズ下界の証明に立ちふさがる障害の解析,パリティを計算するサイズn^2フォーミュラの本質的一意性などの結果を与えることができた。, 22500012
研究期間 2010年 - 2012年 - 最大クリーク抽出アルゴリズムの効率化・拡張と計算量評価および応用
富田 悦次; 高橋 治久; 西野 哲朗; 若月 光夫; 垂井 淳
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(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年 - 組合せ最適化問題の高効率アルゴリズムの開発と評価
富田 悦次; 若月 光夫; 垂井 淳; 高橋 治久
日本学術振興会, 科学研究費助成事業, 電気通信大学, 一般研究(C), 組合せ最適化問題のうちで、先ず、基本的で主要な問題の一つである、グラフ中の最大クリークを厳密に求める問題に対し、単純で高効率な分枝限定アルゴリズムを確立した。そこでは、いかにして分枝の限定を強力に働かせて解の探索領域を小さくするかが高効率化の重要な指標となるが、本研究においては、巧妙な逐次近似彩色-整列法の考案適用により、探索の各段階に於て見出し得る最大クリークの上界を得て分枝制限を効果的に実現し、かつ総実行時間も小さく抑えることに成功した。続いて、更に分枝限定のための種々の方法を考案し、各々の方法の特長が発揮できるようにそれらを組み合せることにより、先の単純なアルゴリズムよりも一層幅広い対象範囲のグラフに対してより効率のよいアルゴリズムを開発した。その高効率性は、ランダムグラフを主とした数多くのグラフに対して実験的比較評価を行うことにより確認した。 更に本手法を、重み付きグラフに対する最大重みクリーク抽出問題に発展させて、新しいアルゴリズムを得、基本的手法に対する有効性を実験的に確認した。 次に、ボルツマンマシンの概念を基にした近似最大クリーク抽出アルゴリズムを基礎として、近似彩色の新しい確率アルゴリズムを開発し、大規模のグラフに対しても効率的にかなり精度よく彩色可能とする手法を提唱し、実験的評価を与えた。 また、組合せ最適化問題の具体例として、RNAの二次構造予測問題を重み付きグラフの最大重みクリーク抽出問題に形式化し、同抽出アルゴリズムによって、基本的なRNAの二次構造予測が可能であることを実験的に確認した。, 06680311
研究期間 1994年 - 1995年
