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
Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences	2007-11-13	Paper
Finding a Duplicate and a Missing Item in a Stream	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

This page was built for person: Jun Tarui