Short Proofs Are Hard to Find
From MaRDI portal
Publication:5091243
DOI10.4230/LIPIcs.ICALP.2019.84OpenAlexW2969433745MaRDI QIDQ5091243
Toniann Pitassi, Yuanhao Wei, Ian Mertz
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10660/pdf/LIPIcs-ICALP-2019-84.pdf
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of clause-learning SAT solvers as resolution engines
- Cutting planes in integer and mixed integer programming
- Polybori: A framework for Gröbner-basis computations with Boolean polynomials
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Non-automatizability of bounded-depth Frege proofs
- On the automatizability of polynomial calculus
- A combinatorial characterization of resolution width
- Global Optimization with Polynomials and the Problem of Moments
- Minimum propositional proof length is NP-hard to linearly approximate
- Proofs as Games
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Simple Constructions of Almost k-wise Independent Random Variables
- Short proofs are narrow—resolution made simple
- On Interpolation and Automatization for Frege Systems
- GRASP: a search algorithm for propositional satisfiability
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Monotone circuit lower bounds from resolution
- Narrow Proofs May Be Maximally Long
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- On the complexity of \(k\)-SAT
This page was built for publication: Short Proofs Are Hard to Find
