Reflections on Proof Complexity and Counting Principles
From MaRDI portal
Publication:5027248
DOI10.1007/978-3-030-71430-7_18OpenAlexW3165859977MaRDI QIDQ5027248
Publication date: 4 February 2022
Published in: Outstanding Contributions to Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-71430-7_18
theory of computationTseitin tautologiescomplexity theorypropositional proof complexitycounting principles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Satisfiability, branch-width and Tseitin tautologies
- On the complexity of cutting-plane proofs
- Exponential lower bounds for the pigeonhole principle
- The intractability of resolution
- Explicit constructions of linear-sized superconcentrators
- On the complexity of regular resolution and the Davis-Putnam procedure
- Lower bounds for the polynomial calculus
- Davis-Putnam resolution versus unrestricted resolution
- Simplified lower bounds for propositional proofs
- Hard examples for the bounded depth Frege proof system
- Cops-robber games and the resolution of Tseitin formulas
- Resolution lower bounds for perfect matching principles
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Dag-like communication and its applications
- Edmonds polytopes and a hierarchy of combinatorial problems
- A Near-Optimal Separation of Regular and General Resolution
- Regular Resolution Versus Unrestricted Resolution
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Many hard examples for resolution
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Expander graphs and their applications
- Outline of an Algorithm for Integer Solutions to Linear Programs and An Algorithm for the Mixed Integer Problem
- A DNF without Regular Shortest Consensus Path
- Hard examples for resolution
- On Cutting Planes
- Approximation and Small-Depth Frege Proofs
- The relative efficiency of propositional proof systems
- Monotone circuits for matching require linear depth
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Short proofs are narrow—resolution made simple
- Extension Complexity of Independent Set Polytopes
- An Average-Case Depth Hierarchy Theorem for Boolean Circuits
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- The Complexity of Propositional Proofs
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
- Communication Complexity
- Semialgebraic Proofs and Efficient Algorithm Design
- Monotone circuit lower bounds from resolution
- Communication lower bounds via critical block sensitivity
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- The Complexity of Propositional Proofs
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- On the power and limitations of branch and cut
This page was built for publication: Reflections on Proof Complexity and Counting Principles
