| 2018 | STACS | Space-Efficient Algorithms for Longest Increasing Subsequence. | Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui |
| 2014 | ISAAC | Depth-First Search Using O(n) Bits. | Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara |
| 2008 | COCOON | Smallest Formulas for Parity of 2k. | Jun Tarui |
| 2008 | TAMC | A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds. | Kazuyuki Amano, Jun Tarui |
| 2007 | TAMC | Linear-Size Log-Depth Negation-Limited Inverter for | Hiroki Morizumi, Jun Tarui |
| 2007 | TAMC | Finding a Duplicate and a Missing Item in a Stream. | Jun Tarui |
| 2006 | ISAAC | Negation-Limited Complexity of Parity and Inverters. | Kazuo Iwama, Hiroki Morizumi, Jun Tarui |
| 2004 | ALT | Learning Boolean Functions in AC | Akinobu Miyata, Jun Tarui, Etsuji Tomita |
| 2003 | STOC | On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. | Toshiya Itoh, Yoshinori Takei, Jun Tarui |
| 2000 | SODA | On permutations with limited independence. | Toshiya Itoh, Yoshinori Takei, Jun Tarui |
| 1999 | ALT | Finding Relevant Variables in PAC Model with Membership Queries. | David Guijarro, Jun Tarui, Tatsuie Tsukiji |
| 1999 | COCOON | On the Negation-Limited Circuit Complexity of Merging. | Kazuyuki Amano, Akira Maruoka, Jun Tarui |
| 1999 | COCOON | Some Observations on the Computational Complexity of Graph Accessibility Problem. | Jun Tarui, Seinosuke Toda |
| 1993 | STACS | Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate. | Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui |
| 1992 | FOCS | The Asymptotic Complexity of Merging Networks | Peter Bro Miltersen, Mike Paterson, Jun Tarui |
| 1992 | ISAAC | On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. | Richard Beigel, Jun Tarui, Seinosuke Toda |
| 1991 | FOCS | On ACC | Richard Beigel, Jun Tarui |
| 1991 | STACS | Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy. | Jun Tarui |