Degree

• MS in Computer Science（University of Rochester）
• MA in Mathematics（University of Rochester）
• PhD in Computer Science（University of Rochester）

Research History

Education

Awards

Others

Papers

• Space-Efficient Algorithms for Longest Increasing Subsequence（2019-01-22） [DOI] [DBLP] [Othres link]
• Space-Efficient Algorithms for Longest Increasing Subsequence（2018-03） [DOI]
• Depth-First Search Using O(n) Bits（2014） [DOI] [Web of Scientce]
• Learning Boolean functions in AC(0) on attribute and classification noise-Estimating an upper bound on attribute and classification noise（2011-08） [DOI] [Web of Scientce]
• A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds（2011-04） [DOI] [Web of Scientce]
• Smallest formulas for the parity of 2(k) variables are essentially unique（2010-06） [DOI] [Web of Scientce]
• Negation-Limited Complexity of Parity and Inverters（2009-06） [DOI] [Web of Scientce]
• Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences（2009） [CiNii Research (CiNii Articles)]
• On the minimum number of completely 3-scrambling permutations（2008-04） [DOI] [Web of Scientce]
• A well-mixed function with circuit complexity 5n +/- o(n): Tightness of the Lachish-Raz-type bounds（2008） [Web of Scientce]
• Smallest formulas for parity of 2(k) variables are essentially unique（2008） [Web of Scientce]
• Reductions for Monotone Boolean Circuits（2008） [DOI]
• Linear-size log-depth negation-limited inverter for k-tonic binary sequences（2007） [Web of Scientce]
• Finding a duplicate and a missing item in a stream（2007） [Web of Scientce]
• Negation-limited complexity of parity and inverters（2006） [Web of Scientce]
• On the Minimum Number of Completely 3-Scrambling Permutations（2005）
• Monotone Boolean Functions with s Zeros Farthest from Threshold Functions（2005）
• Constructing families of epsilon-approximate k-wise independent permutations（2004-05） [Web of Scientce]
• Learning Boolean functions in AC(0) on attribute and classification noise（2004） [Web of Scientce]
• On the negation-limited circuit complexity of merging（2003-03） [Web of Scientce]
• On the Sample Size of k-restricted Min-Wise Independent Permutations and Other k-Wise Distributions（2003） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• A nearly linear size 4-min-wise independent permutation family by finite geometries（2003） [Web of Scientce]
• On permutations with limited independence（2000） [Web of Scientce]
• On complexity of computing the permanent of a rectangular matrix（1999-05） [Web of Scientce]
• Learning DNF by approximating inclusion-exclusion formulae（1999） [Web of Scientce]
• On the Negation-Limited Circuit Complexity of Merging（1999）
• Some observations on the computational complexity of graph accessibility problem（1999） [DOI]
• Finding relevant variables in PAC model with membership queries（1999） [Web of Scientce]
• The asymptotic complexity of merging networks（1996-01） [Web of Scientce]
• On ACC（1994-12） [DOI]
• PROBABILISTIC POLYNOMIALS, AC(0) FUNCTIONS AND THE POLYNOMIAL-TIME HIERARCHY（1993-05） [Web of Scientce]
• Computing Symmetric Functions with AND/OR Circuits and a Single Majority Gate（1993）
• ON PROBABILISTIC ACC CIRCUITS WITH AN EXACT-THRESHOLD OUTPUT GATE（1992） [Web of Scientce]
• ON PROBABILISTIC ACC CIRCUITS WITH AN EXACT-THRESHOLD OUTPUT GATE（1992） [Web of Scientce]
• THE ASYMPTOTIC COMPLEXITY OF MERGING NETWORKS（1992） [Web of Scientce]
• DEGREE COMPLEXITY OF BOOLEAN FUNCTIONS AND ITS APPLICATIONS TO RELATIVIZED SEPARATIONS（1991） [Web of Scientce]
• ON ACC（1991） [Web of Scientce]
• RANDOMIZED POLYNOMIALS, THRESHOLD CIRCUITS, AND THE POLYNOMIAL HIERARCHY（1991） [Web of Scientce]

Misc

• ［京都賞業績紹介］A.C.ヤオ／通信計算量理論：ヤオの卓越した独創の産物（2022-01） [Othres link]
• Google Scholar Profile（2018） [Othres link]
• Google Scholar Profile: http://scholar.google.co.jp/citations?user=7hrsV9cAAAAJ（2018）
• P≠NP予想，代数的計算量（2013-12） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Theory and Applications of Models of Computation 2011 Preface（2013-09） [DOI] [Web of Scientce]
• エキスパンダーとランダムネスの節約・除去（2006） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Recent Progress on Min-Wise Independent Permutations（2003） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]

Presentations

• Expanders and Computational Complexity Theory（2023-09-05）
• ブログは研究に役立つか？どのように？（2016-01-19）
• 計算量理論のいろんな話題（2012-09）
• 計算の複雑さと証明の複雑さ（2012-09）
• Complexity of Finding a Duplicate in a Stream（2012-01）
• DeolalikarのP≠NP論文をめぐって（2010）
• Negation-Limited Complexity of Parity and Inverters（2007）
• 回路計算量の5nの下界に対する5nの上界（2007）
• Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic 0/1 Sequences（2006）
• Explicit Construction of k-Wise Nearly Random Permutations by Iterated Feistel Transform（2004）
• あるノイズモデルにおけるブール関数学習について（2003）
• A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries（2003）
• On the Sample Size of k-Min-Wise Independent Permutations and Other k-Wise Distributions（2002）
• ブール関数のsensitivity, block sensitivity, certificate complexityについて（1998）

Books and Other Publications

• Proceedings of TAMC2011: Theory and Applications of Models of Computation, 8th Annual Conference (Tokyo, Japan, May 23-25, 2011).（2011-05）

Works

Research Projects

Media Coverage

Industrial Property Rights

Professional Memberships

• 情報処理学会
• 電子情報通信学会
• LA シンポジウム
• EATCS
• IEEE
• ACM

Committee Memberships

Teaching Experience

• 情報数理工学実験第二Ａ・Ｂ
• 情報数理工学実験第二Ａ・Ｂ
• Advanced Communication Engineering and Informatics IV (Computational Complexity)
• Advanced Communication Engineering and Informatics IV (Computational Complexity)
• Mathematical Information Science Laboratory ⅡB
• 情報数理工学実験第二B
• Advanced Study for Theoretical Computer Science
• Theory of Computing
• Advanced Communication Engineering and Informatics Ⅲ（Computational Complexity）
• Advanced Communication Engineering and Informatics Ⅲ（Computational Complexity）（学域）
• 理論計算機科学特論
• 計算理論
• Computational Complexity
• 離散数学
• 離散数学
• 理論計算機科学特論
• 理論計算機科学特論
• 計算理論
• 計算理論
• Computational Complexity
• Computational Complexity

Social Contribution

Academic Contribution