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