| Publication | Date of Publication | Type |
|---|
| Local enumeration: the not-all-equal case | 2026-06-24 | Paper |
| Super-linear time-space tradeoff lower bounds for randomized computation | 2026-05-08 | Paper |
| Local enumeration and majority lower bounds | 2026-01-28 | Paper |
| An improved exponential-time algorithm for k-SAT | 2025-10-29 | Paper |
| Time-space tradeoffs for branching programs | 2025-10-29 | Paper |
| Approximating edit distance within constant factor in truly sub-quadratic time | 2025-08-12 | Paper |
| Noisy population recovery in polynomial time | 2025-08-06 | Paper |
| A polynomial time algorithm for lossy population recovery | 2025-05-20 | Paper |
| Estimating the longest increasing sequence in polylogarithmic time | 2025-04-29 | Paper |
| On randomized reductions to the random strings | 2024-07-05 | Paper |
| Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance | 2024-05-14 | Paper |
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
Journal of the ACM | 2022-12-08 | Paper |
| Circuit lower bounds from NP-hardness of MCSP under turing reductions | 2022-07-21 | Paper |
On the rational relationships among pseudo-roots of a non-commutative polynomial
Journal of Pure and Applied Algebra | 2021-03-03 | Paper |
Constant factor approximations to edit distance on far input pairs in nearly linear time
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function
Combinatorica | 2020-10-02 | Paper |
On the discrepancy of random matrices with many columns
Random Structures & Algorithms | 2020-09-16 | Paper |
Lower bounds for combinatorial algorithms for Boolean matrix multiplication
(available as arXiv preprint) | 2020-08-05 | Paper |
On online labeling with large label set
SIAM Journal on Discrete Mathematics | 2019-08-29 | Paper |
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Online labeling: algorithms, lower bounds and open questions | 2018-11-28 | Paper |
| On FKG-type and permanental inequalities | 2018-11-16 | Paper |
Accurate and nearly optimal sublinear approximations to Ulam distance
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Composition limits and separating examples for some Boolean function complexity measures
Combinatorica | 2018-02-22 | Paper |
A communication game related to the sensitivity conjecture
Theory of Computing | 2017-10-11 | Paper |
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Estimating the longest increasing sequence in polylogarithmic time
SIAM Journal on Computing | 2017-05-30 | Paper |
A New Approach to the Sensitivity Conjecture
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
| The power of super-logarithmic number of players | 2017-03-22 | Paper |
On the practically interesting instances of MAXCUT
(available as arXiv preprint) | 2017-01-30 | Paper |
| Towards an algebraic natural proofs barrier via polynomial identity testing | 2017-01-06 | Paper |
Lower bounds for leader election and collective coin-flipping in the perfect information model
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Efficient indexing of necklaces and irreducible polynomials over finite fields
Theory of Computing | 2016-08-22 | Paper |
Low discrepancy sets yield approximate min-wise independent permutation families
Information Processing Letters | 2016-06-16 | Paper |
Hellinger volume and number-on-the-forehead communication complexity
Journal of Computer and System Sciences | 2016-06-13 | Paper |
Tight lower bounds for the online labeling problem
SIAM Journal on Computing | 2015-12-11 | Paper |
Time-space trade-off lower bounds for randomized computation of decision problems
Journal of the ACM | 2015-12-07 | Paper |
A tail bound for read-k families of functions
Random Structures & Algorithms | 2015-10-12 | Paper |
Optimal space distributed move-to-front lists
Proceedings of the tenth annual ACM symposium on Principles of distributed computing - PODC '91 | 2015-06-19 | Paper |
Wait-free <i>k</i>-set agreement is impossible
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Size-depth trade-offs for threshold circuits
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
| Rounds vs queries trade-off in noisy computation | 2014-10-13 | Paper |
Efficient indexing of necklaces and irreducible polynomials over finite fields
Automata, Languages, and Programming | 2014-07-01 | Paper |
Tight lower bounds for the online labeling problem
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
On randomized online labeling with polynomially many labels
Automata, Languages, and Programming | 2013-08-06 | Paper |
On Online Labeling with Polynomially Many Labels
Algorithms – ESA 2012 | 2012-09-25 | Paper |
scientific article; zbMATH DE number 5899292 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
An online algorithm for a problem in scheduling with set-ups and release times
Algorithmica | 2011-05-10 | Paper |
Local monotonicity reconstruction
SIAM Journal on Computing | 2011-04-04 | Paper |
The dual BKR inequality and Rudich's conjecture
Combinatorics, Probability and Computing | 2011-03-07 | Paper |
Lower bounds on the randomized communication complexity of read-once functions
Computational Complexity | 2011-02-18 | Paper |
Local property reconstruction and monotonicity
Property Testing | 2010-10-12 | Paper |
| scientific article; zbMATH DE number 5764799 (Why is no real title available?) | 2010-08-06 | Paper |
Space lower bounds for distance approximation in the data stream model
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
SIAM Journal on Computing | 2009-03-16 | Paper |
The unlabelled speed of a hereditary graph property
Journal of Combinatorial Theory. Series B | 2009-01-21 | Paper |
Lower Bounds for the Noisy Broadcast Problem
SIAM Journal on Computing | 2008-12-22 | Paper |
An improved exponential-time algorithm for <i>k</i> -SAT
Journal of the ACM | 2008-12-21 | Paper |
Approximation algorithms for problems in scheduling with set-ups
Discrete Applied Mathematics | 2008-03-18 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Probabilistic strategies for the partition and plurality problems
Random Structures & Algorithms | 2007-02-07 | Paper |
A localization inequality for set functions.
Journal of Combinatorial Theory. Series A | 2006-05-18 | Paper |
The non-crossing graph
The Electronic Journal of Combinatorics | 2006-01-31 | Paper |
The non-crossing graph
The Electronic Journal of Combinatorics | 2006-01-31 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
A parallel search game
Random Structures & Algorithms | 2005-09-22 | Paper |
A lower bound on the integrality gap for minimum multicut in directed networks
Combinatorica | 2005-02-14 | Paper |
Complexity of some arithmetic problems for binary polynomials
Computational Complexity | 2004-12-13 | Paper |
Multicolour Turán problems
Advances in Applied Mathematics | 2004-10-12 | Paper |
A lower bound on the quantum query complexity of read-once functions
Journal of Computer and System Sciences | 2004-10-01 | Paper |
A limit theorem for sets of stochastic matrices.
Linear Algebra and its Applications | 2004-05-27 | Paper |
| scientific article; zbMATH DE number 1775401 (Why is no real title available?) | 2004-02-08 | Paper |
A lower bound for primality
Journal of Computer and System Sciences | 2003-05-19 | Paper |
The Euclidean distortion of complete binary trees
Discrete & Computational Geometry | 2003-03-17 | Paper |
On list update and work function algorithms.
Theoretical Computer Science | 2003-01-21 | Paper |
Kleitman and combinatorics
Discrete Mathematics | 2002-12-02 | Paper |
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
SIAM Journal on Computing | 2002-09-29 | Paper |
| scientific article; zbMATH DE number 1775444 (Why is no real title available?) | 2002-08-01 | Paper |
Time-space tradeoffs for branching programs
Journal of Computer and System Sciences | 2002-07-04 | Paper |
The efficiency of resolution and Davis-Putnam procedures
SIAM Journal on Computing | 2002-04-23 | Paper |
Sample spaces with small bias on neighborhoods and error-correcting communication protocols
Algorithmica | 2002-04-21 | Paper |
| scientific article; zbMATH DE number 1263224 (Why is no real title available?) | 2002-01-29 | Paper |
| scientific article; zbMATH DE number 1256655 (Why is no real title available?) | 2002-01-17 | Paper |
A decomposition theorem for task systems and bounds for randomized server problems
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1559525 (Why is no real title available?) | 2001-02-28 | Paper |
Exponential lower bounds for depth three Boolean circuits
Computational Complexity | 2000-12-19 | Paper |
| scientific article; zbMATH DE number 1418263 (Why is no real title available?) | 2000-12-03 | Paper |
A correction: Orthogonal representations and connectivity of graphs
Linear Algebra and its Applications | 2000-09-14 | Paper |
Low distortion Euclidean embeddings of trees
Israel Journal of Mathematics | 2000-06-05 | Paper |
Wait-Free <i>k</i>-Set Agreement is Impossible: The Topology of Public Knowledge
SIAM Journal on Computing | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1306867 (Why is no real title available?) | 1999-08-31 | Paper |
\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
Journal of Computer and System Sciences | 1999-05-11 | Paper |
Optimal Space Distributed Order-Preserving Lists
Journal of Algorithms | 1999-05-11 | Paper |
Products and Help Bits in Decision Trees
SIAM Journal on Computing | 1999-02-22 | Paper |
Explicit OR-dispersers with polylogarithmic degree
Journal of the ACM | 1998-12-10 | Paper |
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
Combinatorica | 1998-03-26 | Paper |
Local management of a global resource in a communication network
Journal of the ACM | 1998-01-19 | Paper |
Size--Depth Tradeoffs for Threshold Circuits
SIAM Journal on Computing | 1997-05-26 | Paper |
| scientific article; zbMATH DE number 871902 (Why is no real title available?) | 1996-10-21 | Paper |
Witness sets for families of binary vectors
Journal of Combinatorial Theory. Series A | 1996-02-26 | Paper |
