Propositional proof complexity
From MaRDI portal
Publication:6064569
DOI10.4171/8ecm/03OpenAlexW4384342526MaRDI QIDQ6064569
Publication date: 10 November 2023
Published in: European Congress of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4171/8ecm/03
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regular resolution lower bounds for the weak pigeonhole principle
- Random CNF's are hard for the polynomial calculus
- Exponential lower bounds for the pigeonhole principle
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- The intractability of resolution
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds for the polynomial calculus
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Resolution lower bounds for perfect matching principles
- Resolution with counting: dag-like lower bounds and different moduli
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- On CDCL-based proof systems with the ordered decision strategy
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Many hard examples for resolution
- Hard examples for bounded depth frege
- The relative efficiency of propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Short proofs are narrow—resolution made simple
- A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
- Proof Complexity
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Clique Is Hard on Average for Regular Resolution
- Automating Resolution is NP-Hard
- Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- Logical Foundations of Proof Complexity
- Resolution lower bounds for the weak pigeonhole principle
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
- A new proof of the weak pigeonhole principle
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
This page was built for publication: Propositional proof complexity
