| Publication | Date of Publication | Type |
|---|
| Synergy between circuit obfuscation and circuit minimization | 2025-01-14 | Paper |
| Lower bounds for polynomial calculus with extension variables over finite fields | 2024-11-19 | Paper |
| TFNP characterizations of proof systems and monotone circuits | 2024-09-25 | Paper |
| Stability is stable: connections between replicability, privacy, and adaptive generalization | 2024-05-08 | Paper |
| The fine-grained complexity of multi-dimensional ordering properties | 2024-02-12 | Paper |
| Reproducibility in learning | 2023-12-08 | Paper |
| The power of natural properties as oracles | 2023-08-16 | Paper |
| On the pseudo-deterministic query complexity of NP search problems | 2023-07-12 | Paper |
| On the power and limitations of branch and cut | 2023-07-12 | Paper |
| The fine-grained complexity of multi-dimensional ordering properties | 2022-10-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091000 | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091223 | 2022-07-21 | Paper |
| Fine-grained derandomization: from problem-centric to resource-centric complexity | 2021-07-28 | Paper |
| Agnostic Learning from Tolerant Natural Proofs | 2021-07-28 | Paper |
| Stabbing planes | 2021-06-15 | Paper |
| The surprising power of constant depth algebraic proofs | 2021-01-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5121895 | 2020-09-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5121900 | 2020-09-22 | Paper |
| Does looking inside a circuit help? | 2020-05-26 | Paper |
| Pseudorandomness from shrinkage | 2019-11-21 | Paper |
| A satisfiability algorithm for \(\mathrm{AC}^0\) | 2019-05-10 | Paper |
| Completeness for first-order properties on sparse structures with algorithmic applications | 2019-03-28 | Paper |
| Completeness for first-order properties on sparse structures with algorithmic applications | 2018-07-16 | Paper |
| Pseudorandomness when the odds are against you | 2017-10-10 | Paper |
| Learning algorithms from natural proofs | 2017-10-10 | Paper |
| Tighter connections between derandomization and circuit lower bounds | 2017-08-31 | Paper |
| Fourier concentration from shrinkage | 2017-07-28 | Paper |
| Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations | 2017-07-12 | Paper |
| Simultaneous secrecy and reliability amplification for a general channel model | 2016-12-21 | Paper |
| Linear gaps between degrees for the polynomial calculus modulo distinct primes | 2016-09-29 | Paper |
| Security-preserving hardness-amplification for any regular one-way function | 2016-09-29 | Paper |
| Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space | 2016-09-02 | Paper |
| Pseudorandomness for network algorithms | 2016-09-01 | Paper |
| Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility | 2016-04-15 | Paper |
| Formula Caching in DPLL | 2015-09-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501284 | 2015-08-03 | Paper |
| Size-depth trade-offs for threshold circuits | 2015-05-07 | Paper |
| An axiomatic approach to algebrization | 2015-02-04 | Paper |
| New direct-product testers and \(2\)-query PCPs | 2015-02-04 | Paper |
| Can every randomized algorithm be derandomized? | 2014-11-25 | Paper |
| Extractors and pseudo-random generators with optimal seed length | 2014-09-26 | Paper |
| Designated verifier proofs and their applications | 2014-08-20 | Paper |
| Strong ETH holds for regular resolution | 2014-08-07 | Paper |
| An entropic proof of Chang's inequality | 2014-06-19 | Paper |
| Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space | 2014-05-13 | Paper |
| On the (im)possibility of obfuscating programs | 2014-02-17 | Paper |
| Finding heavy hitters from lossy or noisy data | 2013-10-04 | Paper |
| On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} | 2013-05-16 | Paper |
| New direct-product testers and 2-query PCPs | 2013-03-19 | Paper |
| Toward a model for backtracking and dynamic programming | 2012-06-26 | Paper |
| A stronger model of dynamic programming algorithms | 2011-07-01 | Paper |
| Random CNF's are hard for the polynomial calculus | 2011-02-18 | Paper |
| On the exact complexity of evaluating quantified \(k\)-CNF | 2010-12-07 | Paper |
| Constructive proofs of concentration bounds | 2010-09-10 | Paper |
| Uniform direct product theorems: simplified, optimized, and derandomized | 2010-09-06 | Paper |
| Derandomizing polynomial identity tests means proving circuit lower bounds | 2010-08-16 | Paper |
| Approximate list-decoding of direct product codes and uniform hardness amplification | 2010-04-29 | Paper |
| The complexity of satisfiability of small depth circuits | 2010-01-14 | Paper |
| Models of greedy algorithms for graph problems | 2009-08-27 | Paper |
| A zero-one law for RP and derandomization of AM if NP is not small | 2009-07-15 | Paper |
| Chernoff-type direct product theorems | 2009-06-30 | Paper |
| On the complexity of succinct zero-sum games | 2009-06-17 | Paper |
| Chernoff-Type Direct Product Theorems | 2009-03-10 | Paper |
| Security Amplification for Interactive Cryptographic Primitives | 2009-03-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5302082 | 2009-01-05 | Paper |
| The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs | 2008-03-11 | Paper |
| The resolution complexity of independent sets and vertex covers in random graphs | 2008-03-05 | Paper |
| Extracting Randomness Using Few Independent Sources | 2007-09-07 | Paper |
| Online Algorithms to Minimize Resource Reallocations and Network Communication | 2007-08-28 | Paper |
| Reducing the seed length in the Nisan-Wigderson generator | 2007-05-08 | Paper |
| FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science | 2006-11-14 | Paper |
| Logics for reasoning about cryptographic constructions | 2006-04-28 | Paper |
| Near optimal seperation of tree-like and general resolution | 2005-07-05 | Paper |
| Derandomizing polynomial identity tests means proving circuit lower bounds | 2005-02-23 | Paper |
| A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution | 2005-02-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4737158 | 2004-08-11 | Paper |
| Homogenization and the polynomial calculus | 2004-05-27 | Paper |
| Hill-climbing finds random planted bisections | 2003-07-05 | Paper |
| In search of an easy witness: Exponential time vs. probabilistic polynomial time. | 2003-05-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4783716 | 2002-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4780777 | 2002-11-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4549233 | 2002-08-27 | Paper |
| On the complexity of \(k\)-SAT | 2002-08-14 | Paper |
| Which problems have strongly exponential complexity? | 2002-07-04 | Paper |
| Randomness vs time: Derandomization under a uniform assumption | 2002-07-04 | Paper |
| Communication complexity towards lower bounds on circuit depth | 2002-06-17 | Paper |
| A Note on Conservativity Relations among Bounded Arithmetic Theories | 2002-05-29 | Paper |
| Reducing the complexity of reductions | 2002-05-05 | Paper |
| Linear gaps between degrees for the polynomial calculus modulo distinct primes | 2002-03-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234077 | 2002-01-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2754208 | 2001-11-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527042 | 2001-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526985 | 2001-02-28 | Paper |
| Improved depth lower bounds for small distance connectivity | 2000-10-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4952609 | 2000-05-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252738 | 2000-04-26 | Paper |
| Lower bounds for the polynomial calculus and the Gröbner basis algorithm | 2000-03-30 | Paper |
| A Pseudorandom Generator from any One-way Function | 1999-10-28 | Paper |
| The relative complexity of NP search problems | 1999-09-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4258569 | 1999-09-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252755 | 1999-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228483 | 1999-07-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4250219 | 1999-06-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4251066 | 1999-06-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228469 | 1999-05-18 | Paper |
| Proof complexity in algebraic systems and bounded depth Frege systems with modular counting | 1998-06-29 | Paper |
| Bounding the Size of Planar Intertwines | 1998-02-09 | Paper |
| A tight relationship between generic oracles and type-2 complexity theory | 1997-10-07 | Paper |
| Size--Depth Tradeoffs for Threshold Circuits | 1997-05-26 | Paper |
| Limits on the power of parallel random access machines with weak forms of write conflict resolution | 1997-03-31 | Paper |
| The reachability problem for finite cellular automata | 1997-02-28 | Paper |
| Efficient cryptographic schemes provably as secure as subset sum | 1997-01-26 | Paper |
| Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs | 1996-12-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4281540 | 1996-07-29 | Paper |
| Exponential lower bounds for the pigeonhole principle | 1993-10-18 | Paper |
| On dice and coins: Models of computation for random generation | 1993-08-30 | Paper |
| The effect of random restrictions on formula size | 1993-06-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5750403 | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4732126 | 1989-01-01 | Paper |
