| Publication | Date of Publication | Type |
|---|
Almost optimal superconstant-pass streaming lower bounds for reachability
SIAM Journal on Computing | 2026-09-02 | Paper |
Super-logarithmic lower bounds for dynamic graph problems
SIAM Journal on Computing | 2026-07-08 | Paper |
| Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs | 2026-05-12 | Paper |
| Succinct filters for sets of unknown sizes | 2026-03-18 | Paper |
| Sampling, flowers and communication | 2025-11-04 | Paper |
| Randomized vs. deterministic separation in time-space tradeoffs of multi-output functions | 2025-11-04 | Paper |
| On the amortized complexity of approximate counting | 2025-10-06 | Paper |
| Tight cell-probe lower bounds for dynamic succinct dictionaries | 2025-08-15 | Paper |
| Dynamic ``succincter'' | 2025-08-15 | Paper |
| Super-logarithmic lower bounds for dynamic graph problems | 2025-08-15 | Paper |
| Strong XOR lemma for communication with bounded rounds (extended abstract) | 2025-08-15 | Paper |
| Multi-pass graph streaming lower bounds for cycle counting, MAX-CUT, matching size, and other problems | 2025-08-12 | Paper |
| Amortized dynamic cell-probe lower bounds from four-party communication | 2025-08-06 | Paper |
| On constructing spanners from random Gaussian projections | 2025-01-14 | Paper |
| Dynamic dictionary with subconstant wasted bits per key | 2024-11-28 | Paper |
| Characterizing the multi-pass streaming complexity for solving Boolean CSPs exactly | 2024-09-25 | Paper |
| Towards multi-pass streaming lower bounds for optimal approximation of \textsf{Max-Cut} | 2024-05-14 | Paper |
scientific article; zbMATH DE number 7788449 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Almost optimal super-constant-pass streaming lower bounds for reachability
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Nearly Optimal Static Las Vegas Succinct Dictionary
SIAM Journal on Computing | 2022-05-31 | Paper |
How to Store a Random Walk
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Faster Update Time for Turnstile Streaming Algorithms
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Nearly optimal static Las Vegas succinct dictionary
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Lower bound for succinct range minimum query
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
SIAM Journal on Computing | 2020-10-29 | Paper |
Optimal succinct rank data structure via approximate nonnegative tensor decomposition
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Nearly Optimal Static Las Vegas Succinct Dictionary
(available as arXiv preprint) | 2019-11-04 | Paper |
Optimal lower bounds for distributed and streaming spanning forest computation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Cell-probe lower bounds from online communication complexity
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Finding orthogonal vectors in discrete structures
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Beating brute force for systems of polynomial equations over finite fields
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
SIAM Journal on Computing | 2018-07-04 | Paper |
An improved combinatorial algorithm for Boolean matrix multiplication
Information and Computation | 2018-06-14 | Paper |
| Pruning based Distance Sketches with Provable Guarantees on Random Graphs | 2017-12-22 | Paper |
More applications of the polynomial method to algorithm design
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Finding four-node subgraphs in triangle time
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Cell-probe lower bounds for dynamic problems via a new communication model
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
DecreaseKeys are expensive for external memory priority queues
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
An improved combinatorial algorithm for Boolean matrix multiplication
Lecture Notes in Computer Science | 2015-10-27 | Paper |
Matching triangles and basing hardness on an extremely popular conjecture
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
On a conjecture of Butler and Graham
Designs, Codes and Cryptography | 2013-09-24 | Paper |
A New Variation of Hat Guessing Games
Lecture Notes in Computer Science | 2011-08-17 | Paper |
