Resolution and the binary encoding of combinatorial principles
From MaRDI portal
Publication:5091756
DOI10.4230/LIPIcs.CCC.2019.6OpenAlexW2962833349MaRDI QIDQ5091756
Nicola Galesi, Barnaby Martin, Stefan S. Dantchev
Publication date: 27 July 2022
Full work available at URL: https://arxiv.org/abs/1809.02843
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- Short proofs for tricky formulas
- The intractability of resolution
- Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
- Resolution lower bounds for the weak functional pigeonhole principle.
- Optimality of size-width tradeoffs for resolution
- Computer science logic. 17th international workshop CSL 2003, 12th annual conference of the EACSL, 8th Kurt Gödel colloquium KGC 2003, Vienna, Austria, August 25--30, 2003. Proceedings
- A complexity gap for tree resolution
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- The complexity of proving that a graph is Ramsey
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- On the complexity of resolution with bounded conjunctions
- Short resolution proofs for a sequence of tricky formulas
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Bridging constraint satisfaction and Boolean satisfiability
- Proofs as Games
- A Framework for Space Complexity in Algebraic Proof Systems
- Short proofs are narrow—resolution made simple
- Total Space in Resolution
- Space Complexity in Polynomial Calculus
- Optimality of size-degree tradeoffs for polynomial calculus
- Parameterized Bounded-Depth Frege Is not Optimal
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Clique is hard on average for regular resolution
- Resolution lower bounds for the weak pigeonhole principle
- Parameterized Complexity of DPLL Search Procedures
- A new proof of the weak pigeonhole principle
This page was built for publication: Resolution and the binary encoding of combinatorial principles
