Published papers
Number of published data : 41
No. Classification Refereed paper Title Authorship Author Journal Volume/issue/page Publication date ISSN DOI URL
1 Tutorial
No
Google Scholar Profile:
http://scholar.google.co.jp/citations?user=7hrsV9cAAAAJ
Only
Jun Tarui

0-0
2018



2 Paper
Yes
Space-Efficient Algorithms for Longest Increasing Subsequence
Joint
M. Kiyomi, H. Ono, Y. Otachi, P. Schweitzer and J. Tarui
Theory of Computing Systems
https://doi.org/10.1007/s00224-018-09908-6
First Online:/ 22 January 2019, 1-20
2019/01/22

10.1007/s00224-018-09908-6

3 International conference proceedings, etc.
Yes
Space-Efficient Algorithms for Longest Increasing Subsequence
Joint
M. Kiyomi, H. Ono, Y. Otachi, P. Schweitzer and J. Tarui
Proceedings of STACS2018: 35th International Symposium on Theoretical Aspects of Computer Science
http://www.dagstuhl.de/dagpub/978-3-95977-062-0
44:1-44:15
2018/03



4 International conference proceedings, etc.
Yes
Depth-First Search Using O(n) bits
Joint
T. Asano, T. Izumi, M. Kiyomi, M. Konagaya, H. Ono, Y. Otachi, P. Schweitzer, J. Tarui, R. Uehara
Lecture Notes in Computer Science vol. 8889: Proceedings of ISAAC2014: the 33rd International Symposium on Algorithms and Computation, Springer. doi: 10.1007/978-3-319-13075-0_44
8889, 553-564
2014/12



5 Tutorial
No
P≠NP予想,代数的計算量

垂井淳
数学セミナー12月号:P≠NP予想特集号,2013
18-22
2013/12



6 Paper
Yes
Learning Boolean Functions in AC^0^ on Attribute and Classification Noise

A. Miyata, J. Tarui, and E. Tomita
Theoretical Computer Science. DOI:10.1016/j.tcs.2011.04.047
412/ 35, 4650-4660
2011



7 Paper
Yes
A Well-Mixed Function with Circuit Complexity 5n: Tightness of the Lachish-Raz-type Bounds

K. Amano and J. Tarui
Theoretical Computer Science. DOI:10.1016/j.tcs.2010.12.040
412/ 18, 1646-1651
2011



8 Paper
Yes
Smallest Formulas for the Parity of 2^k^ Variables Are Essentially Unique

Jun Tarui
Theoretical Computer Science.
DOI: 10.1016/j.tcs.2010.03.022
411/ 26-28, 2623-2627
2010



9 Paper
Yes
Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences

H. Morizumi and J. Tarui
Theoretical Computer Science. DOI:10.1016/j.tcs.2008.10.030
410/ 11, 1054-1060
2009



10 Paper
Yes
Negation-Limited Complexity of Parity and Inverters.

K. Iwama, H. Morizumi, and J. Tarui
Algorithmica. DOI: 10.1007/s00453-007-9135-1
54/ 2, 256-267
2009



11 Paper
Yes
Reductions for Monotone Boolean Circuits

K. Iwama, H. Morizumi, and J. Tarui
Theoretical Computer Science. DOI:10.1016/j.tcs.2008.08.009
408, 208-212
2008



12 Paper
Yes
On the Minimum Number of Completely 3-Scrambling Permutations

J. Tarui
Discrete Mathematics. DOI: 10.1016/j.disc.2007.07.069
308/ 8, 1350-1354
2008



13 Tutorial
No
エキスパンダーとランダムネスの節約・除去

垂井淳
数理科学2006年9月号:特集「ランダムネス」,2006.
31-36
2006



14 Paper
Yes
Constructing Families of epsilon-Approximate k-Wise Independent Permutations

T. Itoh, Y. Takei, and J. Tarui
IEICE Transactions on Fundamentals, Vol.E87-A.
993-1103
2004



15 Paper
Yes
On the Negation-Limted Circuit Complexity of Merging

K. Amano, A. Maruoka, and J. Tarui
Discrete Applied Mathematics. DOI: 10.1016/S0166-218X(02)00215-9.
126/ 1, 3-8
2003



16 Paper
Yes
On Complexity of Computing the Permanent of a Rectangular Matrix

T. Kawabata and J. Tarui
IEICE Transactions on Fundamentals, Vol.E82-A, No.5.
741-744
1999



17 Paper
Yes
The Asymptotic Complexity of Merging Networks

P. B. Miltersen, M. Paterson, and J. Tarui
Journal of the ACM. DOI: 10.1145/227595.227693
43/ 1, 147-165
1996



18 Paper
Yes
On ACC

R. Beigel and J. Tarui
Journal of Computational Complexity. DOI: 10.1007/BF01263423
4/ 4, 350-366
1994



19 Paper
Yes
Probabilistic Polynomials, AC^0^ Functions, and the Polynomial Hierarchy

Jun Tarui
Theoretical Computer Science. DOI: 10.1016/0304-3975(93)90214-E
113, 167-183
1993



20 International conference proceedings, etc.
Yes
Smallest Formulas for Parity of 2^k^ Variables Are Essentially Unique

J. Tarui
Lecture Notes in Computer Science vol. 5092: Proc. of COCOON08: The 14th Annual International Computing and Combinatorics Conference, Springer. DOI:10.1007/978-3-540-69733-6_10
LNCS 5092, 92-99
2008



21 International conference proceedings, etc.
Yes
A Well-Mixed Function with Circuit Complexity 5n+-o(n): Tightness of the Lachish-Raz-type Bounds

K. Amano and J. Tarui
Lecture Notes in Computer Science vol. 4978: Proc. of TAMC08: The 5th Annual Conference on Theory and Applications of Models of Computation, Springer. DOI:10.1007/978-3-540-79228-4_30
LNCS 4978, 342-350
2008



22 International conference proceedings, etc.
No
Finding a Duplicate and a Missing Item in a Stream

J. Tarui
Lecture Notes in Computer Science vol. 4484: Proc. of TAMC07: The 4th Annual Conference on Theory and Applications of Models of Computation, Springer. DOI: 10.1007/978-3-540-72504-6_11
LNCS 4484, 128-135
2007



23 International conference proceedings, etc.
Yes
Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences

H. Morizumi and J. Tarui
Lecture Notes in Computer Science vol. 4484: Proc. of TAMC07: The 4th Annual Conference on Theory and Applications of Models of Computation, Springer. DOI: 10.1007/978-3-540-72504-6_54
LNCS 4484, 605-615
2007



24 International conference proceedings, etc.
Yes
Negation-Limited Complexity of Parity and Inverters

K. Iwama, H. Morizumi, and J. Tarui
Lecture Notes in Computer Science vol. 4288: Proc. of ISAAC06: The 25th International Symposium on Algorithms and Computation, Springer. DOI: 10.1007/11940128_24
LNCS 4288, 223-232
2006



25 International conference proceedings, etc.
Yes
Monotone Boolean Functions with s Zeros Farthest from Threshold Functions

K. Amano and J. Tarui
Proc. of EuroComb05: European Conference on Combinatorics, Graph Theory and Applications, Discrete Mathematics & Theoretical Computer Science Conference Volume AE.
11-16
2005



26 International conference proceedings, etc.
Yes
On the Minimum Number of Completely 3-Scrambling Permutations

J. Tarui
Proc. of EuroComb05: European Conference on Combinatorics, Graph Theory and Applications,
Discrete Mathematics & Theoretical Computer Science Conference Volume AE.
351-356
2005



27 International conference proceedings, etc.
No
Learning Boolean Functions in AC^0^ on Attribute and Classification Noise

A. Miyata, J. Tarui, and E. Tomita
Lecture Notes in Computer Science vol. 3244: Proc. of ALT04: Proceedings ot the 15th Algorithmic Learning Theory, Springer. DOI: 10.1007/b100989
142-155
2004



28 International conference proceedings, etc.
No
A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries

J. Tarui, T. Itoh, and Y. Takei
Lecture Notes in Computer Science vol.2764: Proc. of RANDOM03: The 7th International Workshop on Randomization and Approximation Techniques in Computer Science, Springer. DOI: 10.1007/b11961
396-408
2003



29 International conference proceedings, etc.
Yes
On the Sample Size of k-restricted Min-Wise Independent Permutations and Other k-Wise Distributions

T. Itoh, Y. Takei, and J. Tarui
STOC03: Proc. of the 35th Annual ACM Symposium on Theory of Computing, ACM Press. DOI: 10.1145/780542.780645
710-719
2003



30 International conference proceedings, etc.
Yes
On Permutations with Limited Independence

T. Itoh, Y. Takei, and J. Tarui
SODA00: Proc. of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM Press. [ http://doi.acm.org/10.1145/338219.338245 ]
137-146
2000



31 International conference proceedings, etc.
Yes
Finding Relevant Variables in PAC Model with Membership Queries

D. Gijarrao, J. Tarui, and T. Tsukiji
Lecture Notes in Computer Science vol. 1720: Proc. of ALT99: The 10th Internatinal Conference on Algorithmic Learning Theory, Springer. DOI: 10.1007/3-540-46769-6
313-321
1999



32 International conference proceedings, etc.
Yes
Some Obeservations on the Computational Complexity of Graph Accessibility Problem

J. Tarui and S. Toda
Lecture Notes in Computer Science vol. 1627: Proc. of COCOON99: The 5th Annual International Computing and Combinatorics Conference, Springer.
18-30
1999



33 International conference proceedings, etc.
No
On the Negation-Limited Circuit Complexity of Merging

K. Amano, A. Maruoka, and J. Tarui
Lecture Notes in Computer Science vol. 1627: Proc. of COCOON99: The 5th Annual International Computing and Combinatorics Conference, Springer.
204-209
1999



34 International conference proceedings, etc.
Yes
Learning DNF by Approximating Inclusion-Exclusion Formulae

J. Tarui and T. Tsukiji
CoCo99: Proc. of the 14th Annual IEEE Conference on Computational Complexity, IEEE Press. DOI: 10.1109/CCC.
215-221
1999



35 International conference proceedings, etc.
Yes
Computing Symmetric Functions with AND/OR Circuits and a Single Majority Gate

Z. Zhang, D. Barrington, and J. Tarui
Lecture Notes in Computer Science vol. 665: Proc. of STACS93: The 10th Annual Symposium on Theoretical Aspects of Computer Science, Springer. DOI: 10.1007/3-540-56503_53
535-554
1993



36 International conference proceedings, etc.
Yes
The Asymptotic Complexity of Merging Networks

P. B. Miltersen, M. Paterson, and J. Tarui
FOCS92: Proc. of the 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Press. DOI:10.1109/SFCS.1992.267768
236-246
1992



37 International conference proceedings, etc.
Yes
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate

R. Beigel, J. Tarui, and S. Toda
Lecture Notes in Computer Science vol. 650: Proc. of ISAAC92: The 3rd International Symposium on Algorithms and Computation, Springer. DOI: 10.1007/3-540-56279-6_94
420-429
1992



38 International conference proceedings, etc.
Yes
Randomized Polynomials, AC^0^ Functions and the Polynomial Hierarhcy

Jun Tarui
Lecture Notes in Comuter Science vol. 480: Proc. of STACS91: The 8th Annual Symposium on Theoretical Aspects of Computer Science, Springer. DOI: 10.1007/BFb0020802
238-250
1991



39 International conference proceedings, etc.
Yes
On ACC

R. Beigel and J. Tarui
FOCS91: Proc. of the 32nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Press. DOI: 10.1109/SFCS.1991.185449
783-792
1991



40 International conference proceedings, etc.
Yes
Degree Complexity of Boolean Functions and Its Applications to Relativized Separations

Jun Tarui
CoCo91: Proc. of the 6th Annual IEEE Conference on Structures in Complexity Theory, IEEE Press. DOI: 10.1109/SCT.1991.185449
382-390
1991



41 Tutorial
No
Recent Progress on Min-Wise Independent Permutations

T. Itoh, Y. Takei, and J. Tarui
電子情報通信学会コンピュテーション研究会,信学技報COMP2003-49, 2003.
41-50
2003