| Publication | Date of Publication | Type |
|---|
| 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 |
| Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091175 | 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 |
| https://portal.mardi4nfdi.de/entity/Q3299223 | 2020-07-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111865 | 2020-05-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111138 | 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 |
| Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications | 2018-07-16 | Paper |
| Faster Online Matrix-Vector Multiplication | 2018-07-16 | Paper |
| Beating Brute Force for Systems of Polynomial Equations over Finite Fields | 2018-07-16 | Paper |
| Faster decision of first-order graph properties | 2018-04-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4607966 | 2018-03-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4607968 | 2018-03-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601837 | 2018-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4598197 | 2017-12-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4589023 | 2017-11-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368903 | 2017-10-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368736 | 2017-10-10 | Paper |
| More Applications of the Polynomial Method to Algorithm Design | 2017-10-05 | Paper |
| Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity | 2017-10-05 | Paper |
| Finding Four-Node Subgraphs in Triangle Time | 2017-10-05 | Paper |
| Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made | 2017-09-29 | Paper |
| Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits | 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 |
| https://portal.mardi4nfdi.de/entity/Q2934692 | 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 |
| https://portal.mardi4nfdi.de/entity/Q5417690 | 2014-05-22 | Paper |
| Finding, Minimizing, and Counting Weighted Subgraphs | 2013-09-25 | Paper |
| Improving Exhaustive Search Implies Superpolynomial Lower Bounds | 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 |
| https://portal.mardi4nfdi.de/entity/Q2913804 | 2012-09-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3113789 | 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 |
