| Publication | Date of Publication | Type |
|---|
| An algorithmic approach to uniform lower bounds | 2024-11-19 | Paper |
| Why MCSP is a more important problem than SAT (invited talk) | 2024-09-12 | Paper |
| On randomized reductions to the random strings | 2024-07-05 | Paper |
| Constructive separations and their consequences | 2024-07-03 | Paper |
| Learning algorithms versus automatability of Frege systems | 2024-06-24 | Paper |
| A relativization perspective on meta-complexity | 2024-04-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126325 | 2024-04-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126326 | 2024-04-09 | Paper |
| Towards P$\ne$NP from Extended Frege lower bounds | 2023-12-13 | Paper |
| Robustness of average-case meta-complexity via pseudorandomness | 2023-12-08 | Paper |
| On the structure of learnability beyond P/poly | 2023-11-20 | Paper |
| Pseudodeterministic algorithms and the structure of probabilistic time | 2023-11-14 | Paper |
| Strong co-nondeterministic lower bounds for NP cannot be proved feasibly | 2023-11-14 | Paper |
| Iterated lower bound formulas: a diagonalization-based approach to proof complexity | 2023-11-14 | Paper |
| Hardness of KT characterizes parallel cryptography | 2023-07-12 | Paper |
| On the pseudo-deterministic query complexity of NP search problems | 2023-07-12 | Paper |
| Beyond Natural Proofs: Hardness Magnification and Locality | 2023-04-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875775 | 2023-02-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875777 | 2023-02-03 | Paper |
| Hardness magnification near state-of-the-art lower bounds | 2022-07-27 | Paper |
| Parity helps to compute majority | 2022-07-27 | Paper |
| Circuit lower bounds from NP-hardness of MCSP under turing reductions | 2022-07-21 | Paper |
| Expander-Based Cryptography Meets Natural Proofs | 2022-07-18 | Paper |
| Expander-based cryptography meets natural proofs | 2022-04-12 | Paper |
| Hardness magnification near state-of-the-art lower bounds | 2022-02-09 | Paper |
| Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds | 2021-08-04 | Paper |
| Pseudo-derandomizing learning and approximation | 2021-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5121893 | 2020-09-22 | Paper |
| On the average-case complexity of MCSP and its variants | 2020-05-26 | Paper |
| Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness | 2020-05-26 | Paper |
| An average-case lower bound against \(\mathsf{ACC}^0\) | 2020-02-12 | Paper |
| Beyond Natural Proofs: Hardness Magnification and Locality | 2019-11-19 | Paper |
| Average-case lower bounds and satisfiability algorithms for small threshold circuits | 2018-06-15 | Paper |
| Exponential time paradigms through the polynomial time lens | 2018-03-02 | Paper |
| Majority is incompressible by \(\mathrm{AC}^0[p]\) circuits | 2018-01-24 | Paper |
| Average-case lower bounds and satisfiability algorithms for small threshold circuits | 2017-10-10 | Paper |
| New non-uniform lower bounds for uniform classes | 2017-10-10 | Paper |
| Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity | 2017-10-05 | Paper |
| Robust simulations and significant separations | 2017-09-28 | Paper |
| Pseudodeterministic constructions in subexponential time | 2017-08-17 | Paper |
| Exponential lower bounds for \(\mathrm{AC}^0\)-Frege imply superpolynomial Frege lower bounds | 2016-10-24 | Paper |
| Marginal hitting sets imply super-polynomial lower bounds for permanent | 2016-10-07 | Paper |
| Satisfiability on mixed instances | 2016-04-15 | Paper |
| Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP | 2015-11-20 | Paper |
| Pebbles and branching programs for tree evaluation | 2015-09-24 | Paper |
| Uniform derandomization from pathetic lower bounds | 2015-08-21 | Paper |
| On uniformity and circuit lower bounds | 2015-01-23 | Paper |
| On the limits of sparsification | 2013-08-12 | Paper |
| Permanent does not have succinct polynomial size arithmetic circuits of constant depth | 2013-06-06 | Paper |
| Ironic complicity: satisfiability algorithms and circuit lower bounds | 2013-01-28 | Paper |
| Instance compression for the polynomial hierarchy and beyond | 2013-01-07 | Paper |
| The complexity of explicit constructions | 2012-12-07 | Paper |
| Fractional pebbling and thrifty branching programs | 2012-10-24 | Paper |
| Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes | 2012-08-23 | Paper |
| Permanent does not have succinct polynomial size arithmetic circuits of constant depth | 2011-07-06 | Paper |
| Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds | 2011-07-06 | Paper |
| Robust simulations and significant separations | 2011-07-06 | Paper |
| Infeasibility of instance compression and succinct PCPs for NP | 2011-01-18 | Paper |
| Hierarchies for semantic classes | 2010-08-16 | Paper |
| The complexity of explicit constructions | 2010-07-29 | Paper |
| Circuit lower bounds for Merlin-Arthur classes | 2010-07-07 | Paper |
| Branching Programs for Tree Evaluation | 2009-10-16 | Paper |
| Unconditional Lower Bounds against Advice | 2009-07-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549693 | 2009-01-05 | Paper |
| Circuit lower bounds for Merlin-Arthur classes | 2009-01-05 | Paper |
| Some Results on Average-Case Hardness Within the Polynomial Hierarchy | 2008-04-17 | Paper |
| Graph splicing systems | 2006-06-30 | Paper |
| Holographic Proofs and Derandomization | 2005-10-28 | Paper |
| Lower bounds on the complexity of recognizing SAT by Turing machines | 2002-07-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4519733 | 2000-12-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4888430 | 1996-09-24 | Paper |
