Tarui Jun 垂井淳

… Alternative Names

TARUI Jun 垂井淳

垂井淳タルイジュン

Less

Researcher Number	00260539
Other IDs
Affiliation (Current)	2025: 電気通信大学, 大学院情報理工学研究科, 准教授
Affiliation (based on the past Project Information) *help	2016: 電気通信大学, 大学院情報理工学研究科, 准教授 2012 – 2016: 電気通信大学, 情報理工学(系)研究科, 准教授 2010 – 2012: 電気通信大学, 大学院・情報理工学研究科, 准教授 2007 – 2009: The University of Electro-Communications, 電気通信学部, 准教授 2004 – 2007: 電気通信大学, 電気通信学部, 講師 1997 – 1998: 電気通信大学, 電気通信学部, 講師 1994 – 1995: 電気通信大学, 電気通信学部, 講師
Review Section/Research Field	Principal Investigator Fundamental theory of informatics / 計算機科学 / Theory of informatics Except Principal Investigator 計算機科学 / Science and Engineering / Fundamental theory of informatics / Science and Engineering
Keywords	Principal Investigator 計算量理論 / 領域計算量 / 回路計算量 / ブール関数 / 計算量 / ブール関数と多項式 / 多項式表現 / 通信計算量 / 深さ優先探索 / Exponential Time予想 … More / ランダムCNF / 命題論理式に対する証明系 / 証明の長さ / ストリーム計算 / 証明の複雑さ / 計算の複雑さ / pigeonhole principle / finding duplicate / negation-limited inverter / scrambling permutations / ランダムネス / アルゴリズム / 乱拓計算 / ランダマイズドアルゴリズム / sensitivity / 到達可能性判定 / rearrangeability / ハイパーキューブ / permanent / permutation family / PAC learning / DNF / マージング / 否定数限定 / ACC / 比較器回路 / マージ … More Except Principal Investigator アルゴリズム / 分枝限定法 / 最大クリーク / RNA secondary structure prediction / Boltzmann machine / approximate coloring / branch-and-bound / maximum weight clique / maximum clique / algorithm / combinatorial optimization / RNA 2次構造予測 / 確立アルゴリズム / 深さ優先探索 / ポルツマンマシン / RNA2次構造予測 / ボルツマンマシン / 近似彩色 / 最大重みクリーク / 組合せ最適化 / 下界 / 省メモリ / 問題の下界 / 格子グラフ / 最短経路問題 / 作業領域 / グラフアルゴリズム / 計算幾何学 / 計算量 / 分散処理 / DNAコンピューティング / ハイパーグラフ / 計算論的学習理論 / NP困難問題 / 計算機実験 / データマイニング / 多項式時間的可解性 / 時間計算量 / NP完全問題 / 並列処理 / 極大クリーク / Groverのアルゴリズム / 量子回路 / NMR量子計算 / パーマネント / 乗算 / 置換 / 量子論理回路の深さ最小化 / 量子ゲート / 量子ビット / 量子論理回路 / 量子コンピュータ / 量子計算 Less

Study of Circuit Complexity Using Polynomial Representations of Boolean FunctionsPrincipal Investigator
- Principal Investigator
  
  Tarui Jun
- Project Period (FY)
  2013 – 2015
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Theory of informatics
- Research Institution
  The University of Electro-Communications
Exploring the Limits of Computation in the Scenario of Constrained Work Space
- Principal Investigator
  
  Asano Tetsuo
- Project Period (FY)
  2012 – 2016
- Research Category
  
  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
- Review Section
  
  Science and Engineering
- Research Institution
  Japan Advanced Institute of Science and Technology
Propositional Proof Complexity: Analysis fromComputational Complexity PerspectivesPrincipal Investigator
- Principal Investigator
  
  TARUI Jun
- Project Period (FY)
  2010 – 2012
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  The University of Electro-Communications
Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications
- Principal Investigator
  
  TOMITA Etsuji
- Project Period (FY)
  2007 – 2009
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  The University of Electro-Communications
Randomness as Quantitative Computational Resource : Efficient Usage and LimitationsPrincipal Investigator
- Principal Investigator
  
  TARUI Jun
- Project Period (FY)
  2006 – 2008
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  The University of Electro-Communications
量子論理回路の最適化に関する研究
- Principal Investigator
  
  NISHINO Tetsuro
- Project Period (FY)
  2004 – 2007
- Research Category
  
  Grant-in-Aid for Scientific Research on Priority Areas
- Review Section
  
  Science and Engineering
- Research Institution
  The University of Electro-Communications
計算量の理論-下界の証明・計算量の正確な決定・最適アルゴリズムの一意性の問題Principal Investigator
- Principal Investigator
  
  垂井淳
- Project Period (FY)
  1997 – 1998
- Research Category
  
  Grant-in-Aid for Encouragement of Young Scientists (A)
- Research Field
  
  計算機科学
- Research Institution
  The University of Electro-Communications
組合せ論的計算量の理論-特に下界の証明と最適アルゴリズムの-意性の問題Principal Investigator
- Principal Investigator
  
  垂井淳
- Project Period (FY)
  1994 – 1995
- Research Category
  
  Grant-in-Aid for Encouragement of Young Scientists (A)
- Research Field
  
  計算機科学
- Research Institution
  The University of Electro-Communications
Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems
- Principal Investigator
  
  TOMITA Etsuji
- Project Period (FY)
  1994 – 1995
- Research Category
  
  Grant-in-Aid for General Scientific Research (C)
- Research Field
  
  計算機科学
- Research Institution
  The University of Electro-Communications

All 2014 2012 2011 2010 2009 2008 2007 2006 2004 Other

All Journal Article Presentation

[Journal Article] Depth-First Search Using O(n) Bits2014
- Author(s)
  Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara
- Journal Title
  
  Algorithms and Computation Lecture Notes in Computer Science
  
  Volume: 8889 Pages: 553-564
- DOI
  10.1007/978-3-319-13075-0_44
- ISBN
  9783319130743, 9783319130750
- Peer Reviewed
- Data Source
  KAKENHI-PUBLICLY-25104521, KAKENHI-PUBLICLY-25106507, KAKENHI-PROJECT-25330010
[Journal Article] A Well-Mixed Function with Circuit Complexity 5n: Tightness of the Lachish-Raz-type Bounds.2011
- Author(s)
  K. Amano and J. Tarui
- Journal Title
  
  Theoretical Computer Science
  
  Volume: vol.412 Issue: 18 Pages: 1646-1651
- DOI
  10.1016/j.tcs.2010.12.040
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500012
[Journal Article] Learning Boolean Functions in AC0 on Attribute and Classification Noise.2011
- Author(s)
  A. Miyata, J. Tarui, and E. Tomita
- Journal Title
  
  Theoretical Computer Science
  
  Volume: vol412 Issue: 35 Pages: 4650-4660
- DOI
  10.1016/j.tcs.2011.04.047
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500012
[Journal Article] A Well-Mixed Function with Circuit Complexity 5n : Tightnessof the Lachish-Raz-type Bounds2011
- Author(s)
  K.Amano, J.Tarui
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 412 Pages: 1646-1651
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500012
[Journal Article] Smallest Formulas for Parity of 2^k Variables Are Essentially Unique2010
- Author(s)
  Jun Tarui
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 411 Pages: 2623-2627
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500012
[Journal Article] Smallest Formulas for Parity of 2^k Variables Are Essentially Unique.2010
- Author(s)
  Jun Tarui
- Journal Title
  
  Theoretical Computer Science
  
  Volume: vol.411 Issue: 26-28 Pages: 2623-2627
- DOI
  10.1016/j.tcs.2010.03.022
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500012
[Journal Article] Negation-Limited Complexity of Parity and Inverters2009
- Author(s)
  K. Iwama, H. Morizutni, J. Tarui
- Journal Title
  
  Algorithmica 54
  
  Pages: 256-267
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Negation-limited complexity of parity and inverters2009
- Author(s)
  K. Iwama, H. Morizumi, J. Tarui
- Journal Title
  
  Algorithmica 54
  
  Pages: 256-267
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500010
[Journal Article] Linear size log depth negation limited inverter for k-tonic binary sequences2009
- Author(s)
  H. Morizumi and J. Tarui
- Journal Title
  
  Theoretical Computer Science 410(11)
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Reductions for Monotone Boolean Circuits2009
- Author(s)
  K. Iwama, H. Morizumi, J. Tarui
- Journal Title
  
  Theoretical Computer Science 408
  
  Pages: 208-212
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Linear-size log-depth negation-limited inverter for k-tonic binary sequences2009
- Author(s)
  H. Morizumi, J. Tarui
- Journal Title
  
  Theoretical Computer Science 410
  
  Pages: 1054-1060
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500010
[Journal Article] Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences2009
- Author(s)
  H. Morizumi, J. Tarui
- Journal Title
  
  Theoretical Computer Science 410
  
  Pages: 1054-1060
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Negation Limited Complexity of Parity and Inverters2009
- Author(s)
  K. Iwama, H. Morizumi, and J. Tarui
- Journal Title
  
  Algorithmica 54(2)
  
  Pages: 256-267
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Reductions for Monotone Boolean Circuits2008
- Author(s)
  K. Iwama, H. Morizumi, and J. Tarui
- Journal Title
  
  Theoretical Computer Science 408(2-3)
  
  Pages: 208-212
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] On the minimum number of completely 3-scrambling permutations2008
- Author(s)
  J. Tarui
- Journal Title
  
  Discrete Mathematics 308
  
  Pages: 1350-1354
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500010
[Journal Article] Negation-Limited Complexity of Parity and Inverters2008
- Author(s)
  K. Iwama, H. Morizumi, and J. Tarui
- Journal Title
  
  Algorithmica To appear
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] On the Minimum Number of Completely 3-Scrambling Permutations2008
- Author(s)
  J. Tarui
- Journal Title
  
  Discrete Mathematics 308
  
  Pages: 1350-1354
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Reductions for monotone Boolean circuits2008
- Author(s)
  K. Iwama, H. Morizumi, J. Tarui
- Journal Title
  
  Theoretical Computer Science 408
  
  Pages: 208-211
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500010
[Journal Article] On the Minimum Number of Completely 3-scrambling Permutations2008
- Author(s)
  J. Tarui
- Journal Title
  
  Discrete Mathematics 308(8)
  
  Pages: 1350-1354
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Finding a Duplicate and a Missing Item in a Stream2007
- Author(s)
  J.Tarui
- Journal Title
  
  Lecture Notes in Computer Science (TAMC07) 4484
  
  Pages: 128-135
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] On the Minimum Number of Completely 3-Scrambling Permutations2007
- Author(s)
  J.Tarui
- Journal Title
  
  Discrete Mathematics (To appear)
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Finding a Duplicate and a Missing Item in a Stream2007
- Author(s)
  Jun Tarui
- Journal Title
  
  Proc. of TAMC07 : The 4th Annual Conference on Theory and Applications of Models of Computation (to appear)
- Data Source
  KAKENHI-PROJECT-16092208
[Journal Article] Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences2007
- Author(s)
  H.Morizumi, J.Tarui
- Journal Title
  
  Lecture Notes in Computer Science (TAMC07) 4484(To appear)
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Negation-Limited Complexity of Parity and Invertes2007
- Author(s)
  K.Iwama, H.Morizumi, J.Tarui
- Journal Title
  
  Algorithmica(published online Dec 2007, DOI:10.1007/s00453-007-9135-1)
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16092208
[Journal Article] On the Minimum Number of Completely 3-Scrambling Permutations2007
- Author(s)
  J.Tarui
- Journal Title
  
  Discrete Mathematics(published online Nov2007, DOi:10.1016/j.disc.2007.07.069)
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16092208
[Journal Article] Negation-Limited Complexity of Parity and Inverters2006
- Author(s)
  K.Iwama, H.Morizumi, J.Tarui
- Journal Title
  
  Lecture Notes in Computer Science (ISAAC06) 4288
  
  Pages: 223-232
- Data Source
  KAKENHI-PROJECT-18500006
[Journal Article] Constructing Families of epsilon-Approximate k-Wise Independent Permutations2004
- Author(s)
  T.Itoh, Y.Takei, J.Tarui
- Journal Title
  
  IEICE Transactions on Fundamentals vol.E87-Ak, no.5
  
  Pages: 993-1103
- Data Source
  KAKENHI-PROJECT-16092208
[Journal Article] A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds
- Author(s)
  K. Amano, J. Tarui
- Journal Title
  
  Theoretical Computer Science (採録決定)
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500010
[Journal Article] Smallest formulas for the parity of 2k variables are essentially unique
- Author(s)
  J. Tarui
- Journal Title
  
  Theoretical Computer Science (採録決定)
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-19500010
[Presentation] Complexity of Finding a Duplicate in a Stream2012
- Author(s)
  Jun Tarui
- Organizer
  NII Shonan Meeting: Large-scale Distributed Computation
- Place of Presentation
  湘南国際村センター
- Data Source
  KAKENHI-PROJECT-22500012
[Presentation] 計算の複雑さと証明の複雑さ2012
- Author(s)
  垂井淳
- Organizer
  京大数理研研究集会「証明論と複雑性」, 京大数理研講究録
- Place of Presentation
  京都大学数理解析研究所
- Year and Date
  2012-09-12
- Invited
- Data Source
  KAKENHI-PLANNED-24106004
[Presentation] Complexity of Finding a Duplicate in a Stream2012
- Author(s)
  J.Tarui
- Organizer
  Large-scale Distributed Computation (NII Shonan Meeting Jan 12-15, 2012)
- Place of Presentation
  湘南国際村センター(招待講演)
- Year and Date
  2012-01-13
- Data Source
  KAKENHI-PROJECT-22500012
[Presentation] 計算の複雑さと証明の複雑さ2012
- Author(s)
  垂井淳
- Organizer
  研究集会「証明論と複雑性」
- Place of Presentation
  京大数理研究所
- Data Source
  KAKENHI-PROJECT-22500012
[Presentation] 計算の複雑さと証明の複雑さ2012
- Author(s)
  垂井淳
- Organizer
  研究集会「証明論と複雑性」
- Place of Presentation
  京大数理解析研究所
- Invited
- Data Source
  KAKENHI-PROJECT-22500012
[Presentation] DeolalikarのP≠NP論文をめぐって2010
- Author(s)
  垂井淳
- Organizer
  電子情報学会・コンピュテーション研究会
- Place of Presentation
  東北大学青葉山キャンパス
- Year and Date
  2010-10-15
- Data Source
  KAKENHI-PROJECT-22500012
[Presentation] DeolaIikarのP≠NP論文をめぐって2010
- Author(s)
  垂井淳
- Organizer
  電気情報通信学会・コンピュテーション研究会
- Place of Presentation
  東北大学青葉山キャンパス(招待講演
- Year and Date
  2010-10-15
- Data Source
  KAKENHI-PROJECT-22500012
[Presentation] Smallest Formulas for Parity of 2^k Variables Are Essentially Unique2008
- Author(s)
  J. Tarui
- Organizer
  The 14th Annual International Computing and Combinatorics Conference(COCOON08)
- Place of Presentation
  Dalian, China
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Smallest Formulas for Parity of 2k2008
- Author(s)
  J. Tarui
- Organizer
  Proc. of COCOON08
- Place of Presentation
  (LNCS vol 5092)(92-99)
- Year and Date
  2008-06-29
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] A Well-Mixed Function with Circuit Complexity 5n: Tightness of the Lachisch-Raz-Type Bounds.2008
- Author(s)
  K. Amano and J. Tarui
- Organizer
  The 5th Conference on Theory and Applications of Models of Computation(TAMCO8), LNCS.
- Place of Presentation
  Xi'an China
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] A Well-Mixed Function with Circuit Complexity 5n±o(n)2008
- Author(s)
  K. Amano and J. Tarui
- Organizer
  Tightness of the Lachish Raz Type Bounds. Proc. of TAMC08
- Place of Presentation
  LNCS vol 4978, 342-350
- Year and Date
  2008-04-27
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] A Well-Mixed Function with Circuit Complexity 5n : Tightness of the Lachisch-Raz-Type Bounds.2008
- Author(s)
  K. Amano, J. Tarui
- Organizer
  The 5^<th> Conference on Theory and Applications of Models of Computation (TAMC08). LNCS vol. 4978, 342-350, 2008.
- Place of Presentation
  Xi'an China
- Year and Date
  2008-04-27
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Smallest Formulas for Parity of 2^k Variables Are Essentially Unique2008
- Author(s)
  J. Tarui
- Organizer
  rhe 14^<th> Annual International Computing and Combinatorics Conference (COCOON08). LNCS vol. 5092, 92-99, 2008.
- Place of Presentation
  Dalian, China
- Year and Date
  2008-06-29
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences2007
- Author(s)
  H. Morizumi and J. Tarui
- Organizer
  The 4th Conference on Theory and Applicatoins of Models of Computation(TAMC07), LNCS vol. 4484, pp. 605-615, 2007.
- Place of Presentation
  Shanghai, China
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Finding a Duplicate and a Missing Item in a Stream2007
- Author(s)
  J. Tarui
- Organizer
  Proc. of TAMC07
- Place of Presentation
  (LNCS vol 4484)(128-135)
- Year and Date
  2007-05-22
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Linear Size Log Depth Negation Limited Inverter for k Tonic Binary Sequences2007
- Author(s)
  H. Morizumi and J. Tarui
- Organizer
  Proc. of TAMC07
- Place of Presentation
  (LNCS vol 4484)(605-615)
- Year and Date
  2007-05-25
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Finding a Duplicate and a Missing Item in a Stream2007
- Author(s)
  J. Tarui
- Organizer
  The 4th Conference on Theory and Applications of Models of Computation(TAMCO7), LNCS vol.4484, pp. 128-135, 2007.
- Place of Presentation
  Shanghai, China
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Negation Limited Complexity of Parity and Inverters2006
- Author(s)
  K. Iwama, H. Morizumi, and J. Tarui
- Organizer
  Proc. of ISAAC06
- Place of Presentation
  (LNCS vol 4288)(223-232)
- Data Source
  KAKENHI-PROJECT-18500006
[Presentation] Depth-First Search Using O(n) Bits
- Author(s)
  Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Yota Otachi, Hirotaka Ono, Pascal Schweitzer, Jun Tarui and Ryuhei Uehara
- Organizer
  ISAAC2014
- Place of Presentation
  Jeonju, Korea
- Year and Date
  2014-12-15 – 2014-12-17
- Data Source
  KAKENHI-PLANNED-24106004

1. NISHINO Tetsuro (10198484)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
2. TOMITA Etsuji (40016598)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
3. TAKAHASHI Haruhisa (90135418)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
4. WAKATSUKI Mitsuo (30251705)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
5. Asano Tetsuo (90113133)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
6. 太田和夫 (80333491)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
7. 國廣昇 (60345436)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
8. 上原隆平 (00256471)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
9. 小野廣隆 (00346826)

# of Collaborated Projects: 1 results

# of Collaborated Products: 2 results
10. 清見礼 (30447685)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
11. 大舘陽太 (80610196)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
12. Guenter Rote

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
13. Wolfgang Mulzer

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
14. Ovidiu Daescu

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results

Tarui Jun 垂井 淳

TARUI Jun 垂井 淳

垂井 淳 タルイ ジュン

Research Projects

Research Products

Co-Researchers

Study of Circuit Complexity Using Polynomial Representations of Boolean FunctionsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Exploring the Limits of Computation in the Scenario of Constrained Work Space

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Propositional Proof Complexity: Analysis fromComputational Complexity PerspectivesPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Randomness as Quantitative Computational Resource : Efficient Usage and LimitationsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

量子論理回路の最適化に関する研究

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

計算量の理論-下界の証明・計算量の正確な決定・最適アルゴリズムの一意性の問題Principal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

組合せ論的計算量の理論-特に下界の証明と最適アルゴリズムの-意性の問題Principal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

[Journal Article] Depth-First Search Using O(n) Bits2014

Author(s)

Journal Title

DOI

ISBN

Data Source

[Journal Article] A Well-Mixed Function with Circuit Complexity 5n: Tightness of the Lachish-Raz-type Bounds.2011

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Learning Boolean Functions in AC0 on Attribute and Classification Noise.2011

Author(s)

Journal Title

DOI

Data Source

[Journal Article] A Well-Mixed Function with Circuit Complexity 5n : Tightnessof the Lachish-Raz-type Bounds2011

Author(s)

Journal Title

Data Source

Tarui Jun 垂井淳

TARUI Jun 垂井淳

垂井淳タルイジュン