論文
公開件数:41件
No. 種別 査読の有無 標題 単著・共著区分 著者 誌名 巻号頁 出版日 ISSN DOI URL
1 解説

Google Scholar Profile:
http://scholar.google.co.jp/citations?user=7hrsV9cAAAAJ
単著
Jun Tarui

0-0
2018



2 一般論文

Space-Efficient Algorithms for Longest Increasing Subsequence
共著
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 国際会議プロシーディングス等

Space-Efficient Algorithms for Longest Increasing Subsequence
共著
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 国際会議プロシーディングス等

Depth-First Search Using O(n) bits
共著
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 解説

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

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



6 一般論文

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 一般論文

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 一般論文

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 一般論文

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 一般論文

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 一般論文

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 一般論文

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 解説

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

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



14 一般論文

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 一般論文

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 一般論文

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 一般論文

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 一般論文

On ACC

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



19 一般論文

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 国際会議プロシーディングス等

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 解説

Recent Progress on Min-Wise Independent Permutations

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