Jun Tarui
University of Electro-Comm, Tokyo, Japan
email: tarui at ice.uec.ac.jp
Jun Tarui's page in Japanese
Research Interest: Computational Complexity Theory
Selected Publications
-
J. Tarui:
Finding a Duplicate and a Missing Item in a Stream
(pdf)
.
TAMC07-LNCS4484: Proc. of the 4th International
Conference on Theory and Applications of Models of Computation,
LNCS vol. 4484, 128--135, 2007.
-
H. Morizumi, and J. Tarui:
Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary
Sequences
(pdf)
.
TAMC07-LNCS4484: Proc. of the 4th International
Conference on Theory and Applications of Models of Computation,
LNCS vol. 4484, 605--615, 2007.
-
K. Iwama, H. Morizumi, and J. Tarui:
Negation-Limited Complexity of Parity and Inverters.
(pdf)
.
ISAAC06-LNCS4280: Proc. of the 17th International Symposium on Alrorithms
and Computation, LNCS vol. 4280, 223--232, 2006.
-
J. Tarui:
On the Minimum Number of Completely 3-Scrambling
Permutations
(pdf)
.
DMTCS-EuroComb05, 351--356, 2005.
-
K. Amano and J. Tarui:
Monotone Booelan Functions with s Zeros Farthest
from Threshold Functions
(pdf)
.
DMTCS-EuroComb05, 11--16, 2005.
-
A. MIyata, J. Tarui, and E. Tomita:
Learning Boolean Functions in AC0 on Attribute
and Classification Noise.
ALT04-LNCS3244: Proc. of the 15th International Conference on
Algorithmic Learning Theory, 142--155, 2004.
-
T. Itoh, Y. Takei, and J. Tarui:
On the Sample Size of k-restricted Min-Wise
Independent Permutations and Other
k-Wise Distributions
(pdf)
.
STOC03: Proc. of the 35th Annual ACM Symposium on
Theory of Computing,
710--719,
2003.
-
K. Amano, A. Maruoka, and J. Tarui:
On the Negation-Limited Circuit Complexity
of Merging
(pdf)
.
Discrete Applied Mathematics, 3--8, 2003.
-
J. Tarui, T. Itoh, Y. Takei:
A Nearly Linear-Size 4-Min-Wise Independent Permutation Family
by Finite Geometries.
Random-Approx03-LNCS2764, 396--408, 2003.
-
T. Itoh, Y. Takei. and J. Tarui:
On Permutatoins with Limited Independence
(pdf)
.
SODA00: Proc. of the 11th Annual ACM-SIAM Symposium on Discrete
Algorithms,
137--146,
2000.
-
J. Tarui and T. Tsukiji:
Learning DNF by Approximating Inclusion-Exclusion
Formulas
(pdf)
.
CCC99:
Proc. of the 14th IEEE Annual Conference on
Computational Complexity,
215-221,
1999.
-
P. B. Miltersen, M. Paterson, and J. Tarui:
The Asymptotic Complexity of Merging Networks
(pdf)
.
Journal of the ACM, 147--165, 1996.
-
R. Beigel and J. Tarui:
On ACC
(pdf)
.
Computational Complexity, 350--366, 1994.
-
Jun Tarui:
Probabilistic Polynomials, AC0 Functions, and the
Polynomial-Time Hierarchy.
Theoretical Computer Science, 167--183, 1993.
I think my Erdos number is 3:
Paul Erdos --> John Conway --> Mike Paterson --> Jun Traui
Paul Erdos --> Noga Alon --> Peter Bro Miltersen --> Jun Tarui
Paul Erdos --> Noga Alon --> Richard Beigel --> Jun Tarui etc
Jun Tarui
Department of Information and Communication Eng
University of Electro-Communications
Chofu, Tokyo 182-8585