Jun Tarui

According to our database, Jun Tarui authored at least 29 papers between 1991 and 2018.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2018

Space-Efficient Algorithms for Longest Increasing Subsequence.

Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

2014

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

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013

Theory and Applications of Models of Computation 2011.

Mitsunori Ogihara, Jun Tarui

Theor. Comput. Sci., 2013

2011

Learning Boolean functions in AC⁰ on attribute and classification noise - Estimating an upper bound on attribute and classification noise.

Akinobu Miyata, Jun Tarui, Etsuji Tomita

Theor. Comput. Sci., 2011

A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds.

Kazuyuki Amano, Jun Tarui

Theor. Comput. Sci., 2011

2010

Smallest formulas for the parity of 2^k variables are essentially unique.

Jun Tarui

Theor. Comput. Sci., 2010

2009

Linear-size log-depth negation-limited inverter for k-tonic binary sequences.

Hiroki Morizumi, Jun Tarui

Theor. Comput. Sci., 2009

2008

Reductions for monotone Boolean circuits.

Kazuo Iwama, Hiroki Morizumi, Jun Tarui

Theor. Comput. Sci., 2008

On the minimum number of completely 3-scrambling permutations.

Jun Tarui

Discret. Math., 2008

A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds.

Kazuyuki Amano, Jun Tarui

Proceedings of the Theory and Applications of Models of Computation, 2008

Smallest Formulas for Parity of 2k.

Jun Tarui

Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

2007

Finding a Duplicate and a Missing Item in a Stream.

Jun Tarui

Proceedings of the Theory and Applications of Models of Computation, 2007

Linear-Size Log-Depth Negation-Limited Inverter for <i>k</i> -Tonic Binary Sequences.

Hiroki Morizumi, Jun Tarui

Proceedings of the Theory and Applications of Models of Computation, 2007

2006

Negation-Limited Complexity of Parity and Inverters.

Kazuo Iwama, Hiroki Morizumi, Jun Tarui

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2004

Learning Boolean Functions in AC⁰ on Attribute and Classification Noise.

Akinobu Miyata, Jun Tarui, Etsuji Tomita

Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003

On the sample size of k-restricted min-wise independent permutations and other k-wise distributions.

Toshiya Itoh, Yoshinori Takei, Jun Tarui

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries.

Jun Tarui, Toshiya Itoh, Yoshinori Takei

Proceedings of the Approximation, 2003

2000

On permutations with limited independence.

Toshiya Itoh, Yoshinori Takei, Jun Tarui

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

Some Observations on the Computational Complexity of Graph Accessibility Problem.

Jun Tarui, Seinosuke Toda

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

On the Negation-Limited Circuit Complexity of Merging.

Kazuyuki Amano, Akira Maruoka, Jun Tarui

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

Learning DNF by Approximating Inclusion-Exclusion Formulae.

Jun Tarui, Tatsuie Tsukiji

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Finding Relevant Variables in PAC Model with Membership Queries.

David Guijarro, Jun Tarui, Tatsuie Tsukiji

Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999

1993

Probablistic Polynomials, AC0 Functions, and the Polynomial-Time Hierarchy.

Jun Tarui

Theor. Comput. Sci., 1993

Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate.

Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui

Proceedings of the STACS 93, 1993

1992

On Probabilistic ACC Circuits with an Exact-Threshold Output Gate.

Richard Beigel, Jun Tarui, Seinosuke Toda

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

The Asymptotic Complexity of Merging Networks

Peter Bro Miltersen, Mike Paterson, Jun Tarui

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy.

Jun Tarui

Proceedings of the STACS 91, 1991

On ACC

Richard Beigel, Jun Tarui

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Degree Compexity of Boolean Functions and Its Applications to Realivized Separations.

Jun Tarui

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991