Reflections on Proof Complexity and Counting Principles
From MaRDI portal
Recommendations
Cites work
- ``Outline of an algorithm for integer solutions to linear programs and ``An algorithm for the mixed integer problem
- A Computing Procedure for Quantification Theory
- A DNF without Regular Shortest Consensus Path
- A machine program for theorem-proving
- A near-optimal separation of regular and general resolution
- 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
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Approximation and Small-Depth Frege Proofs
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
- Communication Complexity
- Communication lower bounds via critical block sensitivity
- Cops-robber games and the resolution of Tseitin formulas
- Dag-like communication and its applications
- Davis-Putnam resolution versus unrestricted resolution
- Edmonds polytopes and a hierarchy of combinatorial problems
- Expander graphs and their applications
- Explicit constructions of linear-sized superconcentrators
- Exponential lower bounds for the pigeonhole principle
- Extension complexity of independent set polytopes
- Hard examples for resolution
- Hard examples for the bounded depth Frege proof system
- scientific article; zbMATH DE number 5899257 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1179974 (Why is no real title available?)
- scientific article; zbMATH DE number 3313427 (Why is no real title available?)
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Lower bounds for cutting planes proofs with small coefficients
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds for the polynomial calculus
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Many hard examples for resolution
- Monotone circuit lower bounds from resolution
- Monotone circuits for matching require linear depth
- Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- On Cutting Planes
- On the complexity of cutting-plane proofs
- On the complexity of regular resolution and the Davis-Putnam procedure
- On the power and limitations of branch and cut
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Regular Resolution Versus Unrestricted Resolution
- Resolution lower bounds for perfect matching principles
- Satisfiability, branch-width and Tseitin tautologies
- Semialgebraic Proofs and Efficient Algorithm Design
- Short proofs are narrow—resolution made simple
- Simplified lower bounds for propositional proofs
- Stabbing planes
- The Complexity of Propositional Proofs
- The Complexity of Propositional Proofs
- The intractability of resolution
- The relative efficiency of propositional proof systems
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
This page was built for publication: Reflections on Proof Complexity and Counting Principles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5027248)
