| Publication | Date of Publication | Type |
|---|
| Hardness amplification for dynamic binary search trees | 2026-06-08 | Paper |
| Training (overparametrized) neural networks in near-linear time | 2026-04-15 | Paper |
| The complexity of dynamic least-squares regression | 2025-08-15 | Paper |
| Quartic samples suffice for Fourier interpolation | 2025-08-15 | Paper |
| An adaptive step toward the multiphase conjecture | 2025-08-12 | Paper |
| Polynomial data structure lower bounds in the group model | 2025-08-12 | Paper |
| Amortized dynamic cell-probe lower bounds from four-party communication | 2025-08-06 | Paper |
| On the communication complexity of approximate fixed points | 2025-08-06 | Paper |
| Welfare maximization with limited interaction | 2025-08-05 | Paper |
| Direct products in communication complexity | 2025-05-20 | Paper |
| A faster interior-point method for sum-of-squares optimization | 2024-06-24 | Paper |
A faster algorithm for solving general LPs
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
A faster interior-point method for sum-of-squares optimization
Algorithmica | 2023-09-27 | Paper |
A faster interior-point method for sum-of-squares optimization
Algorithmica | 2023-09-27 | Paper |
scientific article; zbMATH DE number 7651207 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
Polynomial data structure lower bounds in the group model
SIAM Journal on Computing | 2022-04-01 | Paper |
| The minrank of random graphs | 2021-07-28 | Paper |
Lower Bounds for Oblivious Near-Neighbor Search
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
How to Store a Random Walk
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
SIAM Journal on Computing | 2020-10-29 | Paper |
Local decodability of the Burrows-Wheeler transform
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Static data structure lower bounds imply rigidity
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | 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 |
The Minrank of Random Graphs
IEEE Transactions on Information Theory | 2018-12-04 | Paper |
ETH hardness for densest-k-subgraph with perfect completeness
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Distributed signaling games
(available as arXiv preprint) | 2018-03-02 | Paper |
Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
SIAM Journal on Computing | 2017-03-10 | Paper |
Information lower bounds via self-reducibility
Theory of Computing Systems | 2017-01-18 | Paper |
A discrepancy lower bound for information complexity
Algorithmica | 2016-11-29 | Paper |
Scale dependence of contact line computations
Mathematical Modelling of Natural Phenomena | 2016-02-19 | Paper |
Welfare and revenue guarantees for competitive bundling equilibrium
Web and Internet Economics | 2016-01-08 | Paper |
The Simultaneous Communication of Disjointness with Applications to Data Streams
Automata, Languages, and Programming | 2015-10-27 | Paper |
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
An interactive information odometer and applications
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
From information to exact communication
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Direct product via round-preserving compression
Automata, Languages, and Programming | 2013-08-06 | Paper |
Information Lower Bounds via Self-reducibility
Computer Science – Theory and Applications | 2013-06-14 | Paper |
A discrepancy lower bound for information complexity
Lecture Notes in Computer Science | 2012-11-02 | Paper |
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
