| 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 |
| https://portal.mardi4nfdi.de/entity/Q6190875 | 2024-02-06 | Paper |
| Data Structures Lower Bounds and Popular Conjectures | 2023-09-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6098772 | 2023-06-14 | Paper |
| Improved Bounds on Fourier Entropy and Min-Entropy | 2023-02-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875642 | 2023-02-03 | Paper |
| Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time | 2022-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5072476 | 2022-04-28 | Paper |
| Improved Bounds on Fourier Entropy and Min-entropy | 2022-03-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5028438 | 2022-02-09 | Paper |
| Circuit complexity of regular languages | 2022-02-04 | Paper |
| Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity | 2021-08-04 | Paper |
| High entropy random selection protocols | 2021-03-26 | Paper |
| Constant factor approximations to edit distance on far input pairs in nearly linear time | 2021-01-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3304119 | 2020-08-05 | Paper |
| Expander construction in \(\mathrm{VNC}^1\) | 2020-06-02 | Paper |
| Stronger lower bounds for online ORAM | 2020-04-30 | Paper |
| Simulation theorems via pseudo-random properties | 2019-12-19 | Paper |
| On Online Labeling with Large Label Set | 2019-08-29 | Paper |
| Simulation beats richness: new data-structure lower bounds | 2019-08-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4967204 | 2019-07-03 | Paper |
| Cover time and mixing time of random walks on dynamic graphs | 2018-09-05 | Paper |
| Expander Construction in VNC1 | 2018-05-03 | Paper |
| Lower Bounds for Elimination via Weak Regularity | 2018-04-19 | Paper |
| Catalytic space: non-determinism and hierarchy | 2018-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601876 | 2018-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368900 | 2017-10-11 | Paper |
| Streaming algorithms for embedding and computing edit distance in the low distance regime | 2017-09-29 | Paper |
| Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates | 2017-06-08 | Paper |
| A New Approach to the Sensitivity Conjecture | 2017-05-19 | Paper |
| Towards a reverse Newman's theorem in interactive information complexity | 2016-11-29 | Paper |
| The Big Match in Small Space | 2016-09-29 | Paper |
| Tight Lower Bounds for the Online Labeling Problem | 2015-12-11 | Paper |
| The Hardness of Being Private | 2015-09-07 | Paper |
| Computing with a full memory | 2015-06-26 | Paper |
| Book review of: Oded Goldreich, Computational complexity: a conceptual perspective | 2014-10-07 | Paper |
| Pseudorandom generators for group products | 2014-06-05 | Paper |
| Exact algorithms for solving stochastic games | 2014-06-05 | Paper |
| Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates | 2014-05-13 | Paper |
| Tight lower bounds for the online labeling problem | 2014-05-13 | Paper |
| On Randomized Online Labeling with Polynomially Many Labels | 2013-08-06 | Paper |
| On Online Labeling with Polynomially Many Labels | 2012-09-25 | Paper |
| Many Random Walks Are Faster Than One | 2011-08-16 | Paper |
| A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\) | 2011-02-18 | Paper |
| The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory | 2011-01-18 | Paper |
| Bounded-depth circuits | 2010-08-16 | Paper |
| Amplifying lower bounds by means of self-reducibility | 2010-07-14 | Paper |
| Does the polynomial hierarchy collapse if onto functions are invertible? | 2010-03-05 | Paper |
| Circuit complexity of regular languages | 2009-10-19 | Paper |
| High Entropy Random Selection Protocols | 2009-02-17 | Paper |
| How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) | 2008-08-28 | Paper |
| Incremental branching programs | 2008-06-17 | Paper |
| Inverting Onto Functions and Polynomial Hierarchy | 2008-06-03 | Paper |
| Circuit Complexity of Regular Languages | 2007-11-13 | Paper |
| STACS 2004 | 2007-10-01 | Paper |
| Languages with Bounded Multiparty Communication Complexity | 2007-09-03 | Paper |
| Incremental Branching Programs | 2007-05-02 | Paper |
| Power from Random Strings | 2006-06-01 | Paper |
| What can be efficiently reduced to the Kolmogorov-random strings? | 2005-12-29 | Paper |
| Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)). | 2003-08-17 | Paper |
| Universal traversal sequences with backtracking. | 2003-05-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4551339 | 2002-09-05 | Paper |
