Proof complexity and the binary encoding of combinatorial principles
From MaRDI portal
Publication:6562831
DOI10.1137/20M134784XMaRDI QIDQ6562831FDOQ6562831
Authors: Stephan Stoyanov Danchev, Nicola Galesi, Abdul Azim Abdul Ghani, 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?)
- Random graphs.
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Threshold functions for small subgraphs
- Title not available (Why is that?)
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Sum-of-squares proofs and the quest toward optimal algorithms
- Probability and Computing
- Title not available (Why is that?)
- Edmonds polytopes and a hierarchy of combinatorial problems
- Title not available (Why is that?)
- Short proofs are narrow—resolution made simple
- The intractability of resolution
- A complexity gap for tree resolution
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Proofs as Games
- Parameterized bounded-depth Frege is not optimal
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
- Resolution lower bounds for the weak functional pigeonhole principle.
- On the weak pigeonhole principle
- The provably total search problems of bounded arithmetic
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
- Short proofs for tricky formulas
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- Space Complexity in Propositional Calculus
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- Title not available (Why is that?)
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Tight rank lower bounds for the Sherali-Adams proof system
- Title not available (Why is that?)
- Bridging constraint satisfaction and Boolean satisfiability
- A new proof of the weak pigeonhole principle
- On the complexity of resolution with bounded conjunctions
- A combinatorial characterization of resolution width
- Optimality of size-degree tradeoffs for polynomial calculus
- Clique is hard on average for regular resolution
- Parameterized Complexity of DPLL Search Procedures
- Optimality of size-width tradeoffs for resolution
- Short resolution proofs for a sequence of tricky formulas
- Tight size-degree bounds for sums-of-squares proofs
- Rank Lower Bounds for the Sherali-Adams Operator
- Resolution lower bounds for the weak pigeonhole principle
- Automating resolution is NP-hard
- Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
- Total space in resolution
- A framework for space complexity in algebraic proof systems
- Narrow proofs may be maximally long
- Space Complexity in Polynomial Calculus
- Sherali-Adams and the binary encoding of combinatorial principles
- On representatives of subsets.
- Resolution and the binary encoding of combinatorial principles
- Sum of squares bounds for the ordering 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)
