| Publication | Date of Publication | Type |
|---|
| Online orthogonal vectors revisited | 2026-07-13 | Paper |
| Circuit depth reductions | 2026-04-15 | Paper |
| On the power of adaptivity for function inversion | 2026-02-03 | Paper |
Polynomial formulations as a barrier for reduction-based hardness proofs
ACM Transactions on Algorithms | 2025-11-03 | Paper |
| Matrix multiplication verification using coding theory | 2025-10-06 | Paper |
| Hilbert functions and low-degree randomness extractors | 2025-10-06 | Paper |
Difficulties constructing lattices with exponential kissing number from codes
IEEE Transactions on Information Theory | 2025-10-06 | Paper |
| Approximability of all finite CSPs with linear sketches | 2025-08-13 | Paper |
| Polynomial data structure lower bounds in the group model | 2025-08-12 | Paper |
| Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT | 2025-08-12 | Paper |
| On the quantitative hardness of CVP | 2025-08-06 | Paper |
| A better-than-3n lower bound for the circuit complexity of an explicit function | 2025-08-06 | Paper |
Sketching approximability of all finite CSPs
Journal of the ACM | 2025-02-06 | Paper |
| The (Im)possibility of simple search-to-decision reductions for approximation problems | 2025-01-14 | Paper |
| Range avoidance for constant depth circuits: hardness and algorithms | 2025-01-14 | Paper |
| Quantum worst-case to average-case reductions for all linear problems | 2024-11-28 | Paper |
| Sketching approximability of (weak) monarchy predicates | 2024-08-22 | Paper |
| Polynomial formulations as a barrier for reduction-based hardness proofs | 2024-05-14 | Paper |
| Lattice problems beyond polynomial time | 2024-05-08 | Paper |
Revisiting time-space tradeoffs for function inversion
Advances in Cryptology – CRYPTO 2023 | 2024-02-02 | Paper |
Improving \(3N\) circuit complexity lower bounds
Computational Complexity | 2024-01-24 | Paper |
scientific article; zbMATH DE number 7788447 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Difficulties Constructing Lattices with Exponential Kissing Number from Codes
(available as arXiv preprint) | 2024-01-01 | Paper |
Linear space streaming lower bounds for approximating CSPs
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Worst-case to average-case reductions via additive combinatorics
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
| The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications | 2023-07-12 | Paper |
Collapsing Superstring Conjecture
(available as arXiv preprint) | 2023-02-03 | Paper |
String Matching: Communication, Circuits, and Learning.
(available as arXiv preprint) | 2023-02-03 | Paper |
The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
Theory of Computing | 2023-01-11 | Paper |
| \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem | 2022-07-21 | 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 |
Data structures meet cryptography: 3SUM with preprocessing
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
(available as arXiv preprint) | 2020-02-20 | Paper |
Static data structure lower bounds imply rigidity
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
The Minrank of Random Graphs
IEEE Transactions on Information Theory | 2018-12-04 | Paper |
Families with infants: speeding up algorithms for NP-hard problems using FFT
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
On the limits of gate elimination
Journal of Computer and System Sciences | 2018-06-06 | Paper |
Tight lower bounds on graph embedding problems
Journal of the ACM | 2018-05-17 | Paper |
| Circuit size lower bounds and \#SAT upper bounds through a general framework | 2018-03-21 | Paper |
| On the limits of gate elimination | 2018-03-21 | Paper |
Gate elimination: circuit size lower bounds and \#SAT upper bounds
Theoretical Computer Science | 2018-03-12 | Paper |
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Lower bounds for the graph homomorphism problem
Automata, Languages, and Programming | 2015-10-27 | Paper |
Condensed Unpredictability
Automata, Languages, and Programming | 2015-10-27 | Paper |
Condensed Unpredictability
Automata, Languages, and Programming | 2015-10-27 | Paper |
A formal treatment of backdoored pseudorandom generators
Advances in Cryptology -- EUROCRYPT 2015 | 2015-09-30 | Paper |
Approximating asymmetric TSP in exponential time
International Journal of Foundations of Computer Science | 2014-07-04 | Paper |
Families with infants: a general approach to solve hard partition problems
Automata, Languages, and Programming | 2014-07-01 | Paper |
Solving SCS for bounded length strings in fewer than \(2^n\) steps
Information Processing Letters | 2014-04-30 | Paper |
New exact algorithms for the 2-constraint satisfaction problem
Theoretical Computer Science | 2014-03-13 | Paper |
Solving 3-superstring in \(3^{n/3}\) time
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
Approximating shortest superstring problem using de Bruijn graphs
Combinatorial Pattern Matching | 2013-06-14 | Paper |
A new algorithm for parameterized MAX-SAT
Parameterized and Exact Computation | 2013-01-07 | Paper |
New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
Parameterized and Exact Computation | 2012-06-15 | Paper |
