Degree Compexity of Boolean Functions and Its Applications to Realivized Separations. - Jun Tarui (SCT, 1991)

Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy. - Jun Tarui (STACS, 1991)

On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. - Richard Beigel; Jun Tarui; Seinosuke Toda (ISAAC, 1992)

Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate. - Zhi-Li Zhang; David A. Mix Barrington; Jun Tarui (STACS, 1993)

Probablistic Polynomials, AC0 Functions, and the Polynomial-Time Hierarchy. - Jun Tarui (Theor. Comput. Sci., 1993)

On ACC. - Richard Beigel; Jun Tarui (Comput. Complex., 1994)

The Asymptotic Complexity of Merging Networks. - Peter Bro Miltersen; Mike Paterson; Jun Tarui (J. ACM, 1996)

Finding Relevant Variables in PAC Model with Membership Queries. - David Guijarro; Jun Tarui; Tatsuie Tsukiji (ALT, 1999)

Learning DNF by Approximating Inclusion-Exclusion Formulae. - Jun Tarui; Tatsuie Tsukiji (CCC, 1999)

Some Observations on the Computational Complexity of Graph Accessibility Problem. - Jun Tarui; Seinosuke Toda (COCOON, 1999)

On permutations with limited independence. - Toshiya Itoh; Yoshinori Takei; Jun Tarui (SODA, 2000)

A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries. - Jun Tarui; Toshiya Itoh; Yoshinori Takei (RANDOM-APPROX, 2003)

On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. - Toshiya Itoh; Yoshinori Takei; Jun Tarui (STOC, 2003)

On the negation-limited circuit complexity of merging. - Kazuyuki Amano; Akira Maruoka; Jun Tarui (Discret. Appl. Math., 2003)

Learning Boolean Functions in AC0 on Attribute and Classification Noise. - Akinobu Miyata; Jun Tarui; Etsuji Tomita (ALT, 2004)

Linear-Size Log-Depth Negation-Limited Inverter for k -Tonic Binary Sequences. - Hiroki Morizumi; Jun Tarui (TAMC, 2007)

Finding a Duplicate and a Missing Item in a Stream. - Jun Tarui (TAMC, 2007)

Smallest Formulas for Parity of 2k. - Jun Tarui (COCOON, 2008)

A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds. - Kazuyuki Amano; Jun Tarui (TAMC, 2008)

On the minimum number of completely 3-scrambling permutations. - Jun Tarui (Discret. Math., 2008)

Reductions for monotone Boolean circuits. - Kazuo Iwama; Hiroki Morizumi; Jun Tarui (Theor. Comput. Sci., 2008)

Negation-Limited Complexity of Parity and Inverters. - Kazuo Iwama; Hiroki Morizumi; Jun Tarui (Algorithmica, 2009)

Linear-size log-depth negation-limited inverter for k-tonic binary sequences. - Hiroki Morizumi; Jun Tarui (Theor. Comput. Sci., 2009)

Smallest formulas for the parity of 2k variables are essentially unique. - Jun Tarui (Theor. Comput. Sci., 2010)

A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds. - Kazuyuki Amano; Jun Tarui (Theor. Comput. Sci., 2011)

Learning Boolean functions in AC0 on attribute and classification noise - Estimating an upper bound on attribute and classification noise. - Akinobu Miyata; Jun Tarui; Etsuji Tomita (Theor. Comput. Sci., 2011)

Theory and Applications of Models of Computation 2011. - Mitsunori Ogihara; Jun Tarui (Theor. Comput. Sci., 2013)

Depth-First Search Using O(n) Bits. - Tetsuo Asano; Taisuke Izumi; Masashi Kiyomi; Matsuo Konagaya; Hirotaka Ono 001; Yota Otachi; Pascal Schweitzer; Jun Tarui; Ryuhei Uehara (ISAAC, 2014)

Space-Efficient Algorithms for Longest Increasing Subsequence. - Masashi Kiyomi; Hirotaka Ono 001; Yota Otachi; Pascal Schweitzer; Jun Tarui (Theory Comput. Syst., 2020)