Jun Tarui

Available identifiers

List of research outcomes

Publication	Date of Publication	Type
Space-Efficient Algorithms for Longest Increasing Subsequence	2020-08-05	Paper
Space-efficient algorithms for longest increasing subsequence	2020-04-15	Paper
Depth-First Search Using $$O(n)$$ Bits	2015-09-11	Paper
Learning Boolean functions in $AC^0$on attribute and classification noise -- estimating an upper bound on attribute and classification noise	2011-09-12	Paper
A well-mixed function with circuit complexity $5n$: tightness of the Lachish-Raz-type bounds	2011-04-05	Paper
On the sample size of k -restricted min-wise independent permutations and other k -wise distributions	2010-08-16	Paper
https://portal.mardi4nfdi.de/entity/Q3576651	2010-07-30	Paper
https://portal.mardi4nfdi.de/entity/Q3576717	2010-07-30	Paper
Smallest formulas for the parity of $2^k$ variables are essentially unique	2010-06-07	Paper
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques	2010-05-26	Paper
Negation-limited complexity of parity and inverters	2009-06-22	Paper
Linear-size log-depth negation-limited inverter for $k$-tonic binary sequences	2009-03-20	Paper
Reductions for monotone Boolean circuits	2008-12-12	Paper
Smallest Formulas for Parity of 2 k Variables Are Essentially Unique	2008-07-10	Paper
A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds	2008-05-27	Paper
Negation-Limited Complexity of Parity and Inverters	2008-04-24	Paper
On the minimum number of completely 3-scrambling permutations	2008-03-18	Paper
Finding a Duplicate and a Missing Item in a Stream	2007-11-13	Paper
Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences	2007-11-13	Paper
Algorithmic Learning Theory	2005-08-18	Paper
On the negation-limited circuit complexity of merging	2003-03-09	Paper
https://portal.mardi4nfdi.de/entity/Q4230345	2002-01-17	Paper
https://portal.mardi4nfdi.de/entity/Q4952610	2001-01-29	Paper
https://portal.mardi4nfdi.de/entity/Q4505382	2000-09-27	Paper
https://portal.mardi4nfdi.de/entity/Q4955321	2000-07-24	Paper
https://portal.mardi4nfdi.de/entity/Q4938656	2000-07-20	Paper
https://portal.mardi4nfdi.de/entity/Q4938666	2000-02-23	Paper
https://portal.mardi4nfdi.de/entity/Q4703465	1999-12-15	Paper
https://portal.mardi4nfdi.de/entity/Q4246733	1999-06-15	Paper
The asymptotic complexity of merging networks	1998-01-19	Paper
On ACC	1995-04-06	Paper
https://portal.mardi4nfdi.de/entity/Q4281556	1994-03-10	Paper
Probabilistic polynomials, AC$^ 0$ functions and the polynomial-time hierarchy	1993-10-17	Paper
https://portal.mardi4nfdi.de/entity/Q4035673	1993-05-18	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Jun Tarui