| Publication | Date of Publication | Type |
|---|
| Streaming \(k\)-edit approximate pattern matching via string decomposition | 2024-11-14 | Paper |
| Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance | 2024-05-14 | Paper |
| Locally consistent decomposition of strings with applications to edit distance sketching | 2024-05-08 | Paper |
| scientific article; zbMATH DE number 7800876 (Why is no real title available?) | 2024-02-06 | Paper |
Data Structures Lower Bounds and Popular Conjectures
(available as arXiv preprint) | 2023-09-20 | Paper |
| scientific article; zbMATH DE number 7695988 (Why is no real title available?) | 2023-06-14 | Paper |
| Improved Bounds on Fourier Entropy and Min-Entropy | 2023-02-07 | Paper |
scientific article; zbMATH DE number 7650307 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
Journal of the ACM | 2022-12-08 | Paper |
| Sorting short integers: the exposition | 2022-04-28 | Paper |
Improved bounds on Fourier entropy and min-entropy
ACM Transactions on Computation Theory | 2022-03-29 | Paper |
Improved bounds on Fourier entropy and min-entropy
ACM Transactions on Computation Theory | 2022-03-29 | Paper |
scientific article; zbMATH DE number 7471677 (Why is no real title available?)
(available as arXiv preprint) | 2022-02-09 | Paper |
| scientific article; zbMATH DE number 7471677 (Why is no real title available?) | 2022-02-09 | Paper |
Circuit complexity of regular languages
Handbook of Automata Theory | 2022-02-04 | Paper |
| Space-optimal quasi-Gray codes with logarithmic read complexity | 2021-08-04 | Paper |
High entropy random selection protocols
Algorithmica | 2021-03-26 | 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 |
Lower bounds for combinatorial algorithms for Boolean matrix multiplication
(available as arXiv preprint) | 2020-08-05 | Paper |
Expander construction in \(\mathrm{VNC}^1\)
Annals of Pure and Applied Logic | 2020-06-02 | Paper |
Stronger lower bounds for online ORAM
(available as arXiv preprint) | 2020-04-30 | Paper |
Simulation theorems via pseudo-random properties
Computational Complexity | 2019-12-19 | Paper |
On online labeling with large label set
SIAM Journal on Discrete Mathematics | 2019-08-29 | Paper |
Simulation beats richness: new data-structure lower bounds
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
| Catalytic computation | 2019-07-03 | Paper |
Cover time and mixing time of random walks on dynamic graphs
Random Structures & Algorithms | 2018-09-05 | Paper |
| Expander construction in \(\mathsf{VNC}^1\) | 2018-05-03 | Paper |
| Lower bounds for elimination via weak regularity | 2018-04-19 | Paper |
Catalytic space: non-determinism and hierarchy
Theory of Computing Systems | 2018-03-01 | Paper |
| scientific article; zbMATH DE number 6829365 (Why is no real title available?) | 2018-01-24 | Paper |
A communication game related to the sensitivity conjecture
Theory of Computing | 2017-10-11 | Paper |
Streaming algorithms for embedding and computing edit distance in the low distance regime
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
A New Approach to the Sensitivity Conjecture
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Towards a reverse Newman's theorem in interactive information complexity
Algorithmica | 2016-11-29 | Paper |
The Big Match in small space (extended abstract)
Algorithmic Game Theory | 2016-09-29 | Paper |
Tight lower bounds for the online labeling problem
SIAM Journal on Computing | 2015-12-11 | Paper |
The hardness of being private
ACM Transactions on Computation Theory | 2015-09-07 | Paper |
Computing with a full memory: catalytic space
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Book review of: Oded Goldreich, Computational complexity: a conceptual perspective
Computer Science Review | 2014-10-07 | Paper |
Pseudorandom generators for group products
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Exact algorithms for solving stochastic games
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | 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 |
Many Random Walks Are Faster Than One
Combinatorics, Probability and Computing | 2011-08-16 | Paper |
A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)
Computational Complexity | 2011-02-18 | Paper |
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Bounded-depth circuits
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Amplifying lower bounds by means of self-reducibility
Journal of the ACM | 2010-07-14 | Paper |
Does the polynomial hierarchy collapse if onto functions are invertible?
Theory of Computing Systems | 2010-03-05 | Paper |
Circuit complexity of regular languages
Theory of Computing Systems | 2009-10-19 | Paper |
High Entropy Random Selection Protocols
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
Automata, Languages and Programming | 2008-08-28 | Paper |
Incremental branching programs
Theory of Computing Systems | 2008-06-17 | Paper |
Inverting Onto Functions and Polynomial Hierarchy
Computer Science – Theory and Applications | 2008-06-03 | Paper |
Circuit Complexity of Regular Languages
Lecture Notes in Computer Science | 2007-11-13 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Languages with Bounded Multiparty Communication Complexity
STACS 2007 | 2007-09-03 | Paper |
Incremental Branching Programs
Computer Science – Theory and Applications | 2007-05-02 | Paper |
Power from Random Strings
SIAM Journal on Computing | 2006-06-01 | Paper |
What can be efficiently reduced to the Kolmogorov-random strings?
Annals of Pure and Applied Logic | 2005-12-29 | Paper |
Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
Theoretical Computer Science | 2003-08-17 | Paper |
Universal traversal sequences with backtracking.
Journal of Computer and System Sciences | 2003-05-14 | Paper |
| scientific article; zbMATH DE number 1796948 (Why is no real title available?) | 2002-09-05 | Paper |
