default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDJun Tarui
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2020
[j13]Masashi Kiyomi
, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui:
Space-Efficient Algorithms for Longest Increasing Subsequence. Theory Comput. Syst. 64(3): 522-541 (2020)
2010 – 2019
- 2018
- [c21]Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui:
Space-Efficient Algorithms for Longest Increasing Subsequence. STACS 2018: 44:1-44:15 - 2017
- [i1]Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui:
Space-Efficient Algorithms for Longest Increasing Subsequence. CoRR abs/1712.09230 (2017) - 2014
- [c20]Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara:
Depth-First Search Using O(n) Bits. ISAAC 2014: 553-564 - 2013
- [j12]Mitsunori Ogihara, Jun Tarui:
Theory and Applications of Models of Computation 2011. Theor. Comput. Sci. 505: 1 (2013) - 2011
- [j11]Kazuyuki Amano, Jun Tarui:
A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds. Theor. Comput. Sci. 412(18): 1646-1651 (2011) - [j10]Akinobu Miyata, Jun Tarui, Etsuji Tomita:
Learning Boolean functions in AC0 on attribute and classification noise - Estimating an upper bound on attribute and classification noise. Theor. Comput. Sci. 412(35): 4650-4660 (2011) - [e1]Mitsunori Ogihara, Jun Tarui:
Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings. Lecture Notes in Computer Science 6648, Springer 2011, ISBN 978-3-642-20876-8 [contents] - 2010
- [j9]Jun Tarui:
Smallest formulas for the parity of 2k variables are essentially unique. Theor. Comput. Sci. 411(26-28): 2623-2627 (2010)
2000 – 2009
- 2009
- [j8]Kazuo Iwama, Hiroki Morizumi, Jun Tarui:
Negation-Limited Complexity of Parity and Inverters. Algorithmica 54(2): 256-267 (2009) - [j7]Hiroki Morizumi, Jun Tarui:
Linear-size log-depth negation-limited inverter for k-tonic binary sequences. Theor. Comput. Sci. 410(11): 1054-1060 (2009) - 2008
- [j6]Jun Tarui:
On the minimum number of completely 3-scrambling permutations. Discret. Math. 308(8): 1350-1354 (2008) - [j5]Kazuo Iwama, Hiroki Morizumi, Jun Tarui:
Reductions for monotone Boolean circuits. Theor. Comput. Sci. 408(2-3): 208-212 (2008) - [c19]Jun Tarui:
Smallest Formulas for Parity of 2k. COCOON 2008: 92-99 - [c18]Kazuyuki Amano, Jun Tarui:
A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds. TAMC 2008: 342-350 - 2007
- [c17]Jun Tarui:
Finding a Duplicate and a Missing Item in a Stream. TAMC 2007: 128-135 - [c16]Hiroki Morizumi, Jun Tarui:
Linear-Size Log-Depth Negation-Limited Inverter for k -Tonic Binary Sequences. TAMC 2007: 605-615 - 2006
- [c15]Kazuo Iwama, Hiroki Morizumi, Jun Tarui:
Negation-Limited Complexity of Parity and Inverters. ISAAC 2006: 223-232 - 2004
- [c14]Akinobu Miyata, Jun Tarui, Etsuji Tomita:
Learning Boolean Functions in AC0 on Attribute and Classification Noise. ALT 2004: 142-155 - 2003
- [j4]Kazuyuki Amano, Akira Maruoka, Jun Tarui:
On the negation-limited circuit complexity of merging. Discret. Appl. Math. 126(1): 3-8 (2003) - [c13]Jun Tarui, Toshiya Itoh, Yoshinori Takei:
A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries. RANDOM-APPROX 2003: 396-408 - [c12]Toshiya Itoh, Yoshinori Takei, Jun Tarui:
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. STOC 2003: 710-719 - 2000
- [c11]Toshiya Itoh, Yoshinori Takei, Jun Tarui:
On permutations with limited independence. SODA 2000: 137-146
1990 – 1999
- 1999
- [c10]David Guijarro, Jun Tarui, Tatsuie Tsukiji:
Finding Relevant Variables in PAC Model with Membership Queries. ALT 1999: 313- - [c9]Jun Tarui, Tatsuie Tsukiji:
Learning DNF by Approximating Inclusion-Exclusion Formulae. CCC 1999: 215- - [c8]Jun Tarui, Seinosuke Toda:
Some Observations on the Computational Complexity of Graph Accessibility Problem. COCOON 1999: 18-30 - [c7]Kazuyuki Amano, Akira Maruoka, Jun Tarui:
On the Negation-Limited Circuit Complexity of Merging. COCOON 1999: 204-209 - 1996
- [j3]Peter Bro Miltersen, Mike Paterson, Jun Tarui:
The Asymptotic Complexity of Merging Networks. J. ACM 43(1): 147-165 (1996) - 1994
- [j2]Richard Beigel, Jun Tarui:
On ACC. Comput. Complex. 4: 350-366 (1994) - 1993
- [j1]Jun Tarui:
Probablistic Polynomials, AC0 Functions, and the Polynomial-Time Hierarchy. Theor. Comput. Sci. 113(1): 167-183 (1993) - [c6]Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui:
Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate. STACS 1993: 535-544 - 1992
- [c5]Peter Bro Miltersen, Mike Paterson, Jun Tarui:
The Asymptotic Complexity of Merging Networks. FOCS 1992: 236-246 - [c4]Richard Beigel, Jun Tarui, Seinosuke Toda:
On Probabilistic ACC Circuits with an Exact-Threshold Output Gate. ISAAC 1992: 420-429 - 1991
- [c3]Jun Tarui:
Degree Compexity of Boolean Functions and Its Applications to Realivized Separations. SCT 1991: 382-390 - [c2]Richard Beigel, Jun Tarui:
On ACC. FOCS 1991: 783-792 - [c1]Jun Tarui:
Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy. STACS 1991: 238-250
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 20:15 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
