 | 2009 |
|---|
| 27 |       | Kazuo Iwama,
Hiroki Morizumi,
Jun Tarui:
Negation-Limited Complexity of Parity and Inverters.
Algorithmica 54(2): 256-267 (2009) |
| 26 | | Hiroki Morizumi,
Jun Tarui:
Linear-size log-depth negation-limited inverter for k-tonic binary sequences.
Theor. Comput. Sci. 410(11): 1054-1060 (2009) |
| 2008 |
|---|
| 25 | | Jun Tarui:
Smallest Formulas for Parity of 2k.
COCOON 2008: 92-99 |
| 24 | | Kazuyuki Amano,
Jun Tarui:
A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds.
TAMC 2008: 342-350 |
| 23 | | Jun Tarui:
On the minimum number of completely 3-scrambling permutations.
Discrete Mathematics 308(8): 1350-1354 (2008) |
| 22 | | Kazuo Iwama,
Hiroki Morizumi,
Jun Tarui:
Reductions for monotone Boolean circuits.
Theor. Comput. Sci. 408(2-3): 208-212 (2008) |
| 2007 |
|---|
| 21 | | Jun Tarui:
Finding a Duplicate and a Missing Item in a Stream.
TAMC 2007: 128-135 |
| 20 | | Hiroki Morizumi,
Jun Tarui:
Linear-Size Log-Depth Negation-Limited Inverter for k -Tonic Binary Sequences.
TAMC 2007: 605-615 |
| 2006 |
|---|
| 19 | | Kazuo Iwama,
Hiroki Morizumi,
Jun Tarui:
Negation-Limited Complexity of Parity and Inverters.
ISAAC 2006: 223-232 |
| 2004 |
|---|
| 18 | | Akinobu Miyata,
Jun Tarui,
Etsuji Tomita:
Learning Boolean Functions in AC0 on Attribute and Classification Noise.
ALT 2004: 142-155 |
| 2003 |
|---|
| 17 | | Jun Tarui,
Toshiya Itoh,
Yoshinori Takei:
A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries.
RANDOM-APPROX 2003: 396-408 |
| 16 | | Toshiya Itoh,
Yoshinori Takei,
Jun Tarui:
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions.
STOC 2003: 710-719 |
| 15 |  | Kazuyuki Amano,
Akira Maruoka,
Jun Tarui:
On the negation-limited circuit complexity of merging.
Discrete Applied Mathematics 126(1): 3-8 (2003) |
| 2000 |
|---|
| 14 | | Toshiya Itoh,
Yoshinori Takei,
Jun Tarui:
On permutations with limited independence.
SODA 2000: 137-146 |
| 1999 |
|---|
| 13 | | David Guijarro,
Jun Tarui,
Tatsuie Tsukiji:
Finding Relevant Variables in PAC Model with Membership Queries.
ATL 1999: 313- |
| 12 | | Jun Tarui,
Seinosuke Toda:
Some Observations on the Computational Complexity of Graph Accessibility Problem.
COCOON 1999: 18-30 |
| 11 | | Kazuyuki Amano,
Akira Maruoka,
Jun Tarui:
On the Negation-Limited Circuit Complexity of Merging.
COCOON 1999: 204-209 |
| 10 | | Jun Tarui,
Tatsuie Tsukiji:
Learning DNF by Approximating Inclusion-Exclusion Formulae.
IEEE Conference on Computational Complexity 1999: 215- |
| 1996 |
|---|
| 9 | | Peter Bro Miltersen,
Mike Paterson,
Jun Tarui:
The Asymptotic Complexity of Merging Networks.
J. ACM 43(1): 147-165 (1996) |
| 1994 |
|---|
| 8 | | Richard Beigel,
Jun Tarui:
On ACC.
Computational Complexity 4: 350-366 (1994) |
| 1993 |
|---|
| 7 | | Zhi-Li Zhang,
David A. Mix Barrington,
Jun Tarui:
Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate.
STACS 1993: 535-544 |
| 6 | | Jun Tarui:
Probablistic Polynomials, AC0 Functions, and the Polynomial-Time Hierarchy.
Theor. Comput. Sci. 113(1): 167-183 (1993) |
| 1992 |
|---|
| 5 | | Peter Bro Miltersen,
Mike Paterson,
Jun Tarui:
The Asymptotic Complexity of Merging Networks
FOCS 1992: 236-246 |
| 4 | | Richard Beigel,
Jun Tarui,
Seinosuke Toda:
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate.
ISAAC 1992: 420-429 |
| 1991 |
|---|
| 3 | | Richard Beigel,
Jun Tarui:
On ACC
FOCS 1991: 783-792 |
| 2 | | Jun Tarui:
Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy.
STACS 1991: 238-250 |
| 1 | | Jun Tarui:
Degree Compexity of Boolean Functions and Its Applications to Realivized Separations.
Structure in Complexity Theory Conference 1991: 382-390 |
