Proof complexity and the binary encoding of combinatorial principles
From MaRDI portal
Publication:6562831
DOI10.1137/20M134784XMaRDI QIDQ6562831
Stefan Dantchev, Abdul Azim Abdul Ghani, Nicola Galesi, Barnaby Martin
Publication date: 27 June 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- Short proofs for tricky formulas
- Tight rank lower bounds for the Sherali-Adams proof system
- 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
- A complexity gap for tree resolution
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Tight size-degree bounds for sums-of-squares proofs
- 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
- Sherali-Adams and the binary encoding of combinatorial principles
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- A combinatorial characterization of resolution width
- Edmonds polytopes and a hierarchy of combinatorial problems
- On representatives of subsets.
- Bridging constraint satisfaction and Boolean satisfiability
- Random graphs.
- Proofs as Games
- On the weak pigeonhole principle
- A framework for space complexity in algebraic proof systems
- Total space in resolution
- Space Complexity in Polynomial Calculus
- Optimality of size-degree tradeoffs for polynomial calculus
- Parameterized Bounded-Depth Frege Is not Optimal
- The provably total search problems of bounded arithmetic
- Space Complexity in Propositional Calculus
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Threshold functions for small subgraphs
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Short proofs are narrow—resolution made simple
- Sum-of-squares proofs and the quest toward optimal algorithms
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Resolution and the binary encoding of combinatorial principles
- Sum of squares bounds for the ordering principle
- Automating Resolution is NP-Hard
- Clique is hard on average for regular resolution
- Narrow Proofs May Be Maximally Long
- Rank Lower Bounds for the Sherali-Adams Operator
- Probability and Computing
- Resolution lower bounds for the weak pigeonhole principle
- LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE
- Parameterized Complexity of DPLL Search Procedures
- A new proof of the weak pigeonhole principle
- Automating algebraic proof systems is NP-hard
This page was built for publication: Proof complexity and the binary encoding of combinatorial principles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6562831)
