| Publication | Date of Publication | Type |
|---|
| https://portal.mardi4nfdi.de/entity/Q6126230 | 2024-04-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126308 | 2024-04-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126349 | 2024-04-09 | Paper |
| Reproducibility in learning | 2023-12-08 | Paper |
| An improved protocol for ExactlyN with more than 3 players | 2023-09-12 | Paper |
| On the power and limitations of branch and cut | 2023-07-12 | Paper |
| On the pseudo-deterministic query complexity of NP search problems | 2023-07-12 | Paper |
| Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes | 2023-04-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875636 | 2023-02-03 | Paper |
| Query-To-Communication Lifting for BPP Using Inner Product | 2022-07-21 | Paper |
| Short Proofs Are Hard to Find | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090432 | 2022-07-18 | Paper |
| Reflections on Proof Complexity and Counting Principles | 2022-02-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4993273 | 2021-06-15 | Paper |
| Towards a complexity-theoretic understanding of restarts in SAT solvers | 2021-04-07 | Paper |
| Query-to-Communication Lifting Using Low-Discrepancy Gadgets | 2021-03-24 | Paper |
| The Surprising Power of Constant Depth Algebraic Proofs | 2021-01-21 | Paper |
| Automating cutting planes is NP-hard | 2021-01-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5121903 | 2020-09-22 | Paper |
| Semialgebraic Proofs and Efficient Algorithm Design | 2020-02-13 | Paper |
| Lifting Nullstellensatz to monotone span programs over any field | 2019-08-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5743425 | 2019-05-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4633844 | 2019-05-06 | Paper |
| Circuit Complexity, Proof Complexity, and Polynomial Identity Testing | 2019-02-25 | Paper |
| Communication Lower Bounds via Critical Block Sensitivity | 2018-11-07 | Paper |
| Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs | 2017-12-19 | Paper |
| Poly-logarithmic Frege depth lower bounds via an expander switching lemma | 2017-09-29 | Paper |
| Strongly exponential lower bounds for monotone computation | 2017-08-17 | Paper |
| On The Communication Complexity of High-Dimensional Permutations | 2017-06-07 | Paper |
| The reusable holdout: Preserving validity in adaptive data analysis | 2017-02-15 | Paper |
| Exponential Lower Bounds for AC 0 -Frege Imply Superpolynomial Frege Lower Bounds | 2016-10-24 | Paper |
| Fairness through awareness | 2016-10-07 | Paper |
| Linear gaps between degrees for the polynomial calculus modulo distinct primes | 2016-09-29 | Paper |
| Upper and Lower Bounds on the Power of Advice | 2016-08-26 | Paper |
| Formula Caching in DPLL | 2015-09-24 | Paper |
| Improved Separations between Nondeterministic and Randomized Multiparty Communication | 2015-09-24 | Paper |
| The Hardness of Being Private | 2015-09-07 | Paper |
| Preserving Statistical Validity in Adaptive Data Analysis | 2015-08-21 | Paper |
| Communication lower bounds via critical block sensitivity | 2015-06-26 | Paper |
| Regular resolution lower bounds for the weak pigeonhole principle | 2015-02-27 | Paper |
| The complexity of analytic tableaux | 2015-02-27 | Paper |
| A new proof of the weak pigeonhole principle | 2014-09-26 | Paper |
| Hardness amplification in proof complexity | 2014-08-13 | Paper |
| Differential privacy under continual observation | 2014-08-13 | Paper |
| Inapproximability of Treewidth and Related Problems | 2014-04-09 | Paper |
| Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems | 2012-11-02 | Paper |
| Toward a model for backtracking and dynamic programming | 2012-06-26 | Paper |
| Special issue in memory of Misha Alekhnovich. Foreword | 2012-06-26 | Paper |
| Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures | 2012-05-30 | Paper |
| Automatizability and Simple Stochastic Games | 2011-07-06 | Paper |
| Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds | 2011-07-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002766 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002781 | 2011-05-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002822 | 2011-05-24 | Paper |
| Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy | 2011-04-04 | Paper |
| The PSPACE-Completeness of Black-White Pebbling | 2011-01-17 | Paper |
| An exponential separation between regular and general resolution | 2010-08-05 | Paper |
| Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table | 2009-03-16 | Paper |
| Improved Separations between Nondeterministic and Randomized Multiparty Communication | 2008-11-27 | Paper |
| Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity | 2008-06-19 | Paper |
| The complexity of resolution refinements | 2008-02-25 | Paper |
| The complexity of properly learning simple concept classes | 2007-11-30 | Paper |
| Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity | 2007-11-28 | Paper |
| A strong direct product theorem for corruption and the multiparty communication complexity of disjointness | 2007-11-14 | Paper |
| Monotone Circuits for the Majority Function | 2007-08-28 | Paper |
| The complexity of analytic tableaux | 2006-11-29 | Paper |
| Automata, Languages and Programming | 2006-01-10 | Paper |
| Regular resolution lower bounds for the weak pigeonhole principle | 2005-07-05 | Paper |
| Non-automatizability of bounded-depth Frege proofs | 2005-02-23 | Paper |
| Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles | 2005-02-21 | Paper |
| Homogenization and the polynomial calculus | 2004-05-27 | Paper |
| A new proof of the weak pigeonhole principle | 2002-09-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542576 | 2002-08-01 | Paper |
| Stochastic Boolean satisfiability | 2002-06-30 | Paper |
| Reducing the complexity of reductions | 2002-05-05 | Paper |
| The Efficiency of Resolution and Davis--Putnam Procedures | 2002-04-23 | 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 |
| Minimum propositional proof length is NP-hard to linearly approximate | 2002-01-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230340 | 2002-01-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2754208 | 2001-11-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2751046 | 2001-10-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527041 | 2001-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527042 | 2001-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4790380 | 2001-01-01 | Paper |
| On Interpolation and Automatization for Frege Systems | 2000-10-18 | Paper |
| Improved depth lower bounds for small distance connectivity | 2000-10-17 | Paper |
| Good degree bounds on Nullstellensatz refutations of the induction principle | 1999-09-29 | Paper |
| The relative complexity of NP search problems | 1999-09-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234107 | 1999-09-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252755 | 1999-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4399249 | 1999-03-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4218098 | 1999-03-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4218929 | 1998-11-15 | Paper |
| Unsolvable systems of equations and proof complexity | 1998-08-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4375795 | 1998-07-08 | Paper |
| Lower bounds for cutting planes proofs with small coefficients | 1998-02-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4353563 | 1997-09-10 | Paper |
| Exponential lower bounds for the tree-like Hajós calculus | 1997-02-28 | Paper |
| Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs | 1996-12-05 | Paper |
| An exponential separation between the parity principle and the pigeonhole principle | 1996-11-25 | Paper |
| The Complexity of the Hajós Calculus | 1996-03-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4850545 | 1995-10-17 | Paper |
| Exponential lower bounds for the pigeonhole principle | 1993-10-18 | Paper |
| Semantics of nondeterministic asynchronous broadcast networks | 1993-08-30 | Paper |
| Approximation and Small-Depth Frege Proofs | 1993-03-09 | Paper |
| A feasibly constructive lower bound for resolution proofs | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3779734 | 1987-01-01 | Paper |
