| Publication | Date of Publication | Type |
|---|
| Faster detours in undirected graphs | 2025-01-06 | Paper |
| On oracles and algorithmic methods for proving lower bounds | 2024-09-25 | Paper |
| Black-Box constructive proofs are unavoidable | 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 | 2024-07-03 | Paper |
| Indistinguishability obfuscation, range avoidance, and bounded arithmetic | 2024-05-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126224 | 2024-04-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126268 | 2024-04-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147361 | 2024-01-15 | Paper |
| Improved Merlin-Arthur protocols for central problems in fine-grained complexity | 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 | 2023-04-27 | Paper |
| Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. | 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 |
| https://portal.mardi4nfdi.de/entity/Q5091175 | 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 | 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 | 2022-02-08 | Paper |
| From circuit complexity to faster all-pairs shortest paths | 2021-08-09 | Paper |
| On super strong ETH | 2021-03-26 | Paper |
| Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions | 2021-02-02 | Paper |
| Sharp threshold results for computational complexity | 2021-01-19 | Paper |
| Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma | 2020-10-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5121894 | 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 | 2020-01-30 | Paper |
| Counting solutions to polynomial systems via reductions | 2019-10-25 | Paper |
| An equivalence class for orthogonal vectors | 2019-10-15 | Paper |
| Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants | 2019-09-10 | Paper |
| Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP | 2019-08-22 | Paper |
| Finding orthogonal vectors in discrete structures | 2019-06-20 | Paper |
| Completeness for first-order properties on sparse structures with algorithmic applications | 2019-03-28 | Paper |
| Subcubic equivalences between path, matrix, and triangle problems | 2019-02-25 | Paper |
| New algorithms and lower bounds for circuits with linear threshold gates | 2019-01-31 | Paper |
| Faster all-pairs shortest paths via circuit complexity | 2018-11-07 | Paper |
| LIMITS and applications of group algebras for parameterized problems | 2018-11-05 | Paper |
| Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky | 2018-07-16 | Paper |
| Beating brute force for systems of polynomial equations over finite fields | 2018-07-16 | Paper |
| Faster Online Matrix-Vector Multiplication | 2018-07-16 | Paper |
| Completeness for first-order properties on sparse structures with algorithmic applications | 2018-07-16 | Paper |
| Faster decision of first-order graph properties | 2018-04-23 | Paper |
| Tight hardness for shortest cycles and paths in sparse graphs | 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 (non) NP-hardness of computing circuit complexity | 2018-01-24 | Paper |
| Deterministic time-space trade-offs for \(k\)-SUM | 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 | 2017-10-11 | Paper |
| Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation | 2017-10-10 | Paper |
| Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity | 2017-10-05 | Paper |
| More applications of the polynomial method to algorithm design | 2017-10-05 | Paper |
| Finding four-node subgraphs in triangle time | 2017-10-05 | Paper |
| Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits | 2017-09-29 | Paper |
| Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made | 2017-09-29 | Paper |
| Thinking algorithmically about impossibility (invited talk) | 2017-08-31 | Paper |
| Probabilistic rank and matrix rigidity | 2017-08-17 | Paper |
| The circuit-input game, natural proofs, and testing circuits with data | 2017-05-19 | Paper |
| Massive online teaching to bounded learners | 2017-05-16 | Paper |
| Natural proofs versus derandomization | 2016-05-12 | Paper |
| Alternation-trading proofs, linear programming, and lower bounds | 2015-09-24 | Paper |
| Limits on alternation trading proofs for time-space lower bounds | 2015-09-21 | Paper |
| Probabilistic Polynomials and Hamming Nearest Neighbors | 2015-07-17 | Paper |
| New algorithms and lower bounds for circuits with linear threshold gates | 2015-06-26 | Paper |
| Faster all-pairs shortest paths via circuit complexity | 2015-06-26 | Paper |
| Finding, minimizing, and counting weighted subgraphs | 2015-02-04 | Paper |
| On uniformity and circuit lower bounds | 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 3-Δ time, with applications | 2014-11-25 | Paper |
| Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications | 2014-11-18 | Paper |
| Losing weight by gaining edges | 2014-10-08 | Paper |
| Nonuniform ACC circuit lower bounds | 2014-09-12 | Paper |
| Improving exhaustive search implies superpolynomial lower bounds | 2014-08-13 | Paper |
| Natural proofs versus derandomization | 2014-08-07 | Paper |
| Regularity Lemmas and Combinatorial Algorithms | 2014-07-25 | Paper |
| On the possibility of faster \textsc{SAT} algorithms | 2014-05-22 | Paper |
| Improving exhaustive search implies superpolynomial lower bounds | 2013-09-25 | Paper |
| Finding, minimizing, and counting weighted subgraphs | 2013-09-25 | Paper |
| Amplifying circuit lower bounds against polynomial time, with applications | 2013-07-19 | Paper |
| Towards NEXP versus BPP? | 2013-06-14 | Paper |
| Regularity lemmas and combinatorial algorithms | 2012-09-27 | Paper |
| Improved parameterized algorithms for above average constraint satisfaction | 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 | 2011-12-15 | Paper |
| Diagonalization strikes back: some recent lower bounds in complexity theory | 2011-08-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002808 | 2011-05-24 | Paper |
| Parallelizing time with polynomial circuits | 2011-04-01 | Paper |
| Resolving the Complexity of Some Data Privacy Problems | 2010-09-07 | Paper |
| Confronting hardness using a hybrid approach | 2010-08-16 | Paper |
| Finding paths of length \(k\) in \(O^{*}(2^k)\) time | 2010-06-16 | Paper |
| Theory and Applications of Satisfiability Testing | 2009-07-24 | Paper |
| An Improved Time-Space Lower Bound for Tautologies | 2009-07-23 | Paper |
| Limits and Applications of Group Algebras for Parameterized Problems | 2009-07-14 | Paper |
| Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems | 2009-03-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549658 | 2009-01-05 | Paper |
| A New Combinatorial Approach for Sparse Graph Problems | 2008-08-28 | Paper |
| Time-space tradeoffs for counting NP solutions modulo integers | 2008-08-20 | Paper |
| Inductive time-space lower bounds for SAT and related problems | 2007-11-14 | Paper |
| A new algorithm for optimal 2-constraint satisfaction and its implications | 2006-01-09 | Paper |
| Automata, Languages and Programming | 2005-08-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828947 | 2004-11-29 | Paper |
