On acc R Beigel, J Tarui Computational Complexity 4 (4), 350-366, 1994 | 260 | 1994 |

Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy J Tarui Theoretical computer science 113 (1), 167-183, 1993 | 113* | 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 | 47 | 2014 |

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

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

Finding relevant variables in PAC model with membership queries D Guijarro, J Tarui, T Tsukiji International Conference on Algorithmic Learning Theory, 313-322, 1999 | 23 | 1999 |

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

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

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 | 20 | 1992 |

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 | 19 | 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 | 19 | 2003 |

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

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

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

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

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 | 11 | 2011 |

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

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 | 8 | 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 |

Negation-limited complexity of parity and inverters K Iwama, H Morizumi, J Tarui Algorithmica 54 (2), 256-267, 2009 | 6 | 2009 |