On acc R Beigel, J Tarui computational complexity 4, 350-366, 1994 | 273 | 1994 |

Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy J Tarui Theoretical computer science 113 (1), 167-183, 1993 | 119* | 1993 |

Depth-first search using bits T Asano, T Izumi, M Kiyomi, M Konagaya, H Ono, Y Otachi, P Schweitzer, ... International Symposium on Algorithms and Computation, 553-564, 2014 | 51 | 2014 |

Learning DNF by approximating inclusion-exclusion formulae J Tarui, T Tsukiji Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity …, 1999 | 33 | 1999 |

The asymptotic complexity of merging networks PB Miltersen, M Paterson, J Tarui Journal of the ACM (JACM) 43 (1), 147-165, 1996 | 33 | 1996 |

On permutations with limited independence T Itoh, Y Takei, J Tarui Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms …, 2000 | 24 | 2000 |

On probabilistic ACC circuits with an exact-threshold output gate R Beigel, J Tarui, S Toda International Symposium on Algorithms and Computation, 420-429, 1992 | 24 | 1992 |

Finding relevant variables in PAC model with membership queries D Guijarro, J Tarui, T Tsukiji Algorithmic Learning Theory: 10th International Conference, ALT’99 Tokyo …, 1999 | 23 | 1999 |

Degree complexity of Boolean functions and its applications to relativized separations J Tarui 1991 Proceedings of the Sixth Annual Structure in Complexity Theory …, 1991 | 23 | 1991 |

On the sample size of *k*-restricted min-wise independent permutations and other *k*-wise distributionsT Itoh, Y Takei, J Tarui Proceedings of the thirty-fifth annual ACM symposium on Theory of computing …, 2003 | 20 | 2003 |

On the sample size of *k*-restricted min-wise independent permutations and other *k*-wise distributionsT Itoh, Y Takei, J Tarui Proceedings of the thirty-fifth annual ACM symposium on Theory of computing …, 2003 | 20 | 2003 |

On the minimum number of completely 3-scrambling permutations J Tarui Discrete mathematics 308 (8), 1350-1354, 2008 | 16 | 2008 |

On the negation-limited circuit complexity of merging K Amano, A Maruoka, J Tarui Discrete Applied Mathematics 126 (1), 3-8, 2003 | 15 | 2003 |

A well-mixed function with circuit complexity 5n: Tightness of the Lachish–Raz-type bounds K Amano, J Tarui Theoretical computer science 412 (18), 1646-1651, 2011 | 12 | 2011 |

Finding a duplicate and a missing item in a stream J Tarui Theory and Applications of Models of Computation: 4th International …, 2007 | 12 | 2007 |

Computing symmetric functions with *AND/OR* circuits and a single *MAJORITY* gateZL Zhang, DAM Barrington, J Tarui Annual Symposium on Theoretical Aspects of Computer Science, 535-544, 1993 | 11 | 1993 |

Space-efficient algorithms for longest increasing subsequence M Kiyomi, H Ono, Y Otachi, P Schweitzer, J Tarui 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), 2018 | 10 | 2018 |

Smallest formulas for the parity of 2k variables are essentially unique J Tarui Theoretical computer science 411 (26-28), 2623-2627, 2010 | 8 | 2010 |

On complexity of computing the permanent of a rectangular matrix T Kawabata, J Tarui IEICE transactions on fundamentals of electronics, communications and …, 1999 | 8 | 1999 |

A nearly linear size 4-min-wise independent permutation family by finite geometries J Tarui, T Itoh, Y Takei International Workshop on Randomization and Approximation Techniques in …, 2003 | 7 | 2003 |