| Publication | Date of Publication | Type |
|---|
| A VLSI circuit model accounting for wire delay | 2025-11-04 | Paper |
| Towards stronger depth lower bounds | 2025-11-04 | Paper |
| Derandomization vs refutation: a unified framework for characterizing derandomization | 2025-08-15 | Paper |
| MAJORITY-3SAT (and related problems) in polynomial time | 2025-08-13 | Paper |
| Constructive separations and their consequences | 2025-08-13 | Paper |
| Almost-everywhere circuit lower bounds from non-trivial derandomization | 2025-08-12 | Paper |
| Hardness magnification for all sparse NP languages | 2025-08-12 | Paper |
| Distributed PCP theorems for hardness of approximation in P | 2025-08-06 | Paper |
| Polynomial representations of threshold functions and algorithmic applications | 2025-08-06 | Paper |
| Probabilistic polynomials and Hamming nearest neighbors | 2025-08-05 | Paper |
| Subcubic equivalences between path, matrix and triangle problems | 2025-04-29 | Paper |
| Faster detours in undirected graphs | 2025-01-06 | Paper |
| Black-Box constructive proofs are unavoidable | 2024-09-25 | Paper |
| On oracles and algorithmic methods for proving lower bounds | 2024-09-25 | Paper |
| On the number of quantifiers as a complexity measure | 2024-08-06 | Paper |
| Truly low-space element distinctness and subset sum via pseudorandom hash functions | 2024-07-19 | Paper |
Constructive separations and their consequences
TheoretiCS | 2024-07-03 | Paper |
| Indistinguishability obfuscation, range avoidance, and bounded arithmetic | 2024-05-08 | Paper |
| scientific article; zbMATH DE number 7829235 (Why is no real title available?) | 2024-04-09 | Paper |
scientific article; zbMATH DE number 7829270 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
scientific article; zbMATH DE number 7788444 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Improved Merlin-Arthur protocols for central problems in fine-grained complexity
Algorithmica | 2023-08-17 | Paper |
| Black-Box Hypotheses and Lower Bounds | 2023-08-08 | Paper |
Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
Theory of Computing Systems | 2023-04-27 | Paper |
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
(available as arXiv preprint) | 2023-02-07 | Paper |
| Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity | 2022-07-27 | Paper |
| Relations and equivalences between circuit lower bounds and karp-lipton theorems | 2022-07-27 | Paper |
| scientific article; zbMATH DE number 7561519 (Why is no real title available?) | 2022-07-21 | Paper |
| Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors | 2022-07-21 | Paper |
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
(available as arXiv preprint) | 2022-07-18 | Paper |
| Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle | 2022-07-18 | Paper |
| Some estimated likelihoods for computational complexity | 2022-02-16 | Paper |
Deterministic APSP, Orthogonal Vectors, and More
ACM Transactions on Algorithms | 2022-02-08 | Paper |
From circuit complexity to faster all-pairs shortest paths
SIAM Review | 2021-08-09 | Paper |
On super strong ETH
Journal of Artificial Intelligence Research | 2021-03-26 | Paper |
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Sharp threshold results for computational complexity
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
SIAM Journal on Computing | 2020-10-29 | Paper |
scientific article; zbMATH DE number 7250146 (Why is no real title available?)
(available as arXiv preprint) | 2020-09-22 | Paper |
| The polynomial method in circuit complexity applied to algorithm design (invited talk) | 2020-07-19 | Paper |
| Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants | 2020-05-27 | Paper |
| Easiness amplification and uniform circuit lower bounds | 2020-05-26 | Paper |
| On super strong ETH | 2020-05-20 | Paper |
Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
| Counting solutions to polynomial systems via reductions | 2019-10-25 | Paper |
An equivalence class for orthogonal vectors
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
Algorithmica | 2019-09-10 | Paper |
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
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 |
Completeness for first-order properties on sparse structures with algorithmic applications
ACM Transactions on Algorithms | 2019-03-28 | Paper |
Subcubic equivalences between path, matrix, and triangle problems
Journal of the ACM | 2019-02-25 | Paper |
New algorithms and lower bounds for circuits with linear threshold gates
Theory of Computing | 2019-01-31 | Paper |
Faster all-pairs shortest paths via circuit complexity
SIAM Journal on Computing | 2018-11-07 | Paper |
LIMITS and applications of group algebras for parameterized problems
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | 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 |
Faster Online Matrix-Vector Multiplication
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Completeness for first-order properties on sparse structures with algorithmic applications
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Faster decision of first-order graph properties
Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | 2018-04-23 | Paper |
| Tight hardness for shortest cycles and paths in sparse graphs | 2018-03-15 | Paper |
Tight hardness for shortest cycles and paths in sparse graphs
(available as arXiv preprint) | 2018-03-15 | Paper |
| On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity | 2018-03-15 | Paper |
On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
(available as arXiv preprint) | 2018-03-15 | Paper |
| On the (non) NP-hardness of computing circuit complexity | 2018-01-24 | Paper |
Deterministic time-space trade-offs for \(k\)-SUM
(available as arXiv preprint) | 2017-12-19 | Paper |
| Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable | 2017-11-06 | Paper |
On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
Theory of Computing | 2017-10-11 | Paper |
Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
(available as arXiv preprint) | 2017-10-10 | Paper |
Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | 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 |
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| Thinking algorithmically about impossibility (invited talk) | 2017-08-31 | Paper |
Probabilistic rank and matrix rigidity
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
The circuit-input game, natural proofs, and testing circuits with data
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Massive online teaching to bounded learners
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Natural proofs versus derandomization
SIAM Journal on Computing | 2016-05-12 | Paper |
Alternation-trading proofs, linear programming, and lower bounds
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Limits on alternation trading proofs for time-space lower bounds
Computational Complexity | 2015-09-21 | Paper |
| Probabilistic Polynomials and Hamming Nearest Neighbors | 2015-07-17 | Paper |
Faster all-pairs shortest paths via circuit complexity
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
New algorithms and lower bounds for circuits with linear threshold gates
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Finding, minimizing, and counting weighted subgraphs
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
On uniformity and circuit lower bounds
Computational Complexity | 2015-01-23 | Paper |
| Matrix-vector multiplication in sub-quadratic time (some preprocessing required) | 2014-12-18 | Paper |
Finding a maximum weight triangle in n <sup>3-Δ</sup> time, with applications
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Finding heaviest H-subgraphs in real weighted graphs, with applications
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Losing weight by gaining edges
Algorithms - ESA 2014 | 2014-10-08 | Paper |
Nonuniform ACC circuit lower bounds
Journal of the ACM | 2014-09-12 | Paper |
Improving exhaustive search implies superpolynomial lower bounds
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Natural proofs versus derandomization
Proceedings of the forty-fifth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Regularity Lemmas and Combinatorial Algorithms
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
| On the possibility of faster \textsc{SAT} algorithms | 2014-05-22 | Paper |
Improving exhaustive search implies superpolynomial lower bounds
SIAM Journal on Computing | 2013-09-25 | Paper |
Finding, minimizing, and counting weighted subgraphs
SIAM Journal on Computing | 2013-09-25 | Paper |
Amplifying circuit lower bounds against polynomial time, with applications
Computational Complexity | 2013-07-19 | Paper |
Towards NEXP versus BPP?
Computer Science – Theory and Applications | 2013-06-14 | Paper |
Regularity lemmas and combinatorial algorithms
Theory of Computing | 2012-09-27 | Paper |
Improved parameterized algorithms for above average constraint satisfaction
Parameterized and Exact Computation | 2012-06-15 | Paper |
| Alternation-trading proofs, linear programming, and lower bounds (extended abstract) | 2012-01-23 | Paper |
An improved time-space lower bound for tautologies
Journal of Combinatorial Optimization | 2011-12-15 | Paper |
Diagonalization strikes back: some recent lower bounds in complexity theory
Lecture Notes in Computer Science | 2011-08-17 | Paper |
scientific article; zbMATH DE number 5899282 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
Parallelizing time with polynomial circuits
Theory of Computing Systems | 2011-04-01 | Paper |
Resolving the Complexity of Some Data Privacy Problems
Automata, Languages and Programming | 2010-09-07 | Paper |
Confronting hardness using a hybrid approach
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Finding paths of length \(k\) in \(O^{*}(2^k)\) time
Information Processing Letters | 2010-06-16 | Paper |
Theory and Applications of Satisfiability Testing
Lecture Notes in Computer Science | 2009-07-24 | Paper |
An Improved Time-Space Lower Bound for Tautologies
Lecture Notes in Computer Science | 2009-07-23 | Paper |
Limits and Applications of Group Algebras for Parameterized Problems
Automata, Languages and Programming | 2009-07-14 | Paper |
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
Automata, Languages and Programming | 2009-03-12 | Paper |
| scientific article; zbMATH DE number 5485494 (Why is no real title available?) | 2009-01-05 | Paper |
A New Combinatorial Approach for Sparse Graph Problems
Automata, Languages and Programming | 2008-08-28 | Paper |
Time-space tradeoffs for counting NP solutions modulo integers
Computational Complexity | 2008-08-20 | Paper |
Inductive time-space lower bounds for SAT and related problems
Computational Complexity | 2007-11-14 | Paper |
A new algorithm for optimal 2-constraint satisfaction and its implications
Theoretical Computer Science | 2006-01-09 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
| scientific article; zbMATH DE number 2119676 (Why is no real title available?) | 2004-11-29 | Paper |
