Jun Tarui

36 papers A* 4A 4B 5C 4Misc 3Journal 14Unranked 2
YearRankTypeTitle / Venue / Authors
2020 J jnl
Space-Efficient Algorithms for Longest Increasing Subsequence.
Theory Comput. Syst.
Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui
2018 A conf
Space-Efficient Algorithms for Longest Increasing Subsequence.
STACS
Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui
2017 J jnl
Space-Efficient Algorithms for Longest Increasing Subsequence.
CoRR
Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui
2014 B conf
Depth-First Search Using O(n) Bits.
ISAAC
Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara
2013 J jnl
Theory and Applications of Models of Computation 2011.
Theor. Comput. Sci.
Mitsunori Ogihara, Jun Tarui
2011 J jnl
A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds.
Theor. Comput. Sci.
Kazuyuki Amano, Jun Tarui
2011 J jnl
Learning Boolean functions in AC
Theor. Comput. Sci.
Akinobu Miyata, Jun Tarui, Etsuji Tomita
2011 C ed.
Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings
TAMC
Mitsunori Ogihara, Jun Tarui
2010 J jnl
Smallest formulas for the parity of 2
Theor. Comput. Sci.
Jun Tarui
2009 J jnl
Linear-size log-depth negation-limited inverter for k-tonic binary sequences.
Theor. Comput. Sci.
Hiroki Morizumi, Jun Tarui
2009 J jnl
Negation-Limited Complexity of Parity and Inverters.
Algorithmica
Kazuo Iwama, Hiroki Morizumi, Jun Tarui
2008 C conf
A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds.
TAMC
Kazuyuki Amano, Jun Tarui
2008 J jnl
On the minimum number of completely 3-scrambling permutations.
Discret. Math.
Jun Tarui
2008 J jnl
Reductions for monotone Boolean circuits.
Theor. Comput. Sci.
Kazuo Iwama, Hiroki Morizumi, Jun Tarui
2008 Misc conf
Smallest Formulas for Parity of 2k.
COCOON
Jun Tarui
2007 C conf
Finding a Duplicate and a Missing Item in a Stream.
TAMC
Jun Tarui
2007 C conf
Linear-Size Log-Depth Negation-Limited Inverter for
TAMC
Hiroki Morizumi, Jun Tarui
2006 B conf
Negation-Limited Complexity of Parity and Inverters.
ISAAC
Kazuo Iwama, Hiroki Morizumi, Jun Tarui
2004 B conf
Learning Boolean Functions in AC
ALT
Akinobu Miyata, Jun Tarui, Etsuji Tomita
2003 — conf
A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries.
RANDOM-APPROX
Jun Tarui, Toshiya Itoh, Yoshinori Takei
2003 J jnl
On the negation-limited circuit complexity of merging.
Discret. Appl. Math.
Kazuyuki Amano, Akira Maruoka, Jun Tarui
2003 A* conf
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions.
STOC
Toshiya Itoh, Yoshinori Takei, Jun Tarui
2000 A* conf
On permutations with limited independence.
SODA
Toshiya Itoh, Yoshinori Takei, Jun Tarui
1999 B conf
Finding Relevant Variables in PAC Model with Membership Queries.
ALT
David Guijarro, Jun Tarui, Tatsuie Tsukiji
1999 A conf
Learning DNF by Approximating Inclusion-Exclusion Formulae.
CCC
Jun Tarui, Tatsuie Tsukiji
1999 Misc conf
On the Negation-Limited Circuit Complexity of Merging.
COCOON
Kazuyuki Amano, Akira Maruoka, Jun Tarui
1999 Misc conf
Some Observations on the Computational Complexity of Graph Accessibility Problem.
COCOON
Jun Tarui, Seinosuke Toda
1996 J jnl
The Asymptotic Complexity of Merging Networks.
J. ACM
Peter Bro Miltersen, Mike Paterson, Jun Tarui
1994 J jnl
On ACC.
Comput. Complex.
Richard Beigel, Jun Tarui
1993 A conf
Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate.
STACS
Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui
1993 J jnl
Probablistic Polynomials, AC0 Functions, and the Polynomial-Time Hierarchy.
Theor. Comput. Sci.
Jun Tarui
1992 B conf
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate.
ISAAC
Richard Beigel, Jun Tarui, Seinosuke Toda
1992 A* conf
The Asymptotic Complexity of Merging Networks
FOCS
Peter Bro Miltersen, Mike Paterson, Jun Tarui
1991 — conf
Degree Compexity of Boolean Functions and Its Applications to Realivized Separations.
SCT
Jun Tarui
1991 A* conf
On ACC
FOCS
Richard Beigel, Jun Tarui
1991 A conf
Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy.
STACS
Jun Tarui