On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
From MaRDI portal
Publication:6649455
DOI10.1145/3531130.3533344MaRDI QIDQ6649455
Ilario Bonacina, Maria Luisa Bonet
Publication date: 6 December 2024
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exponential lower bounds for the pigeonhole principle
- The relative complexity of NP search problems
- Simplified lower bounds for propositional proofs
- An exponential separation between the parity principle and the pigeonhole principle
- Sherali-Adams and the binary encoding of combinatorial principles
- Circular (yet sound) proofs
- Propositional proof systems based on maximum satisfiability
- On transformations of constant depth propositional proofs
- Equivalence between systems stronger than resolution
- Towards a better understanding of (partial weighted) MaxSAT proof systems
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- The relative efficiency of propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- Proof Complexity Meets Algebra
- 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
- Strongly exponential lower bounds for monotone computation
- Semialgebraic Proofs and Efficient Algorithm Design
- Lifting Nullstellensatz to monotone span programs over any field
- Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations
- The power of negative reasoning
This page was built for publication: On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6649455)
