Perfect matching in random graphs is as hard as Tseitin
From MaRDI portal
(Redirected from Publication:6562700)
Perfect matching in random graphs is as hard as Tseitin (scientific article; zbMATH DE number 7872058)
Perfect matching in random graphs is as hard as Tseitin (scientific article; zbMATH DE number 7872058)
bounded-depth Fregeperfect matchingpolynomial calculusproof complexitysum of squarestopological embedding
Complexity of proofs (03F20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- Resolution complexity of perfect matching principles for sparse graphs
- Tight lower bounds on the resolution complexity of perfect matching principles
- Perfect matching for regular graphs is AC^ 0-hard for the general matching problem
- Resolution lower bounds for perfect matching principles
- Space complexity of random formulae in resolution
Cites work
- A generalized method for proving polynomial calculus degree lower bounds
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A proof of Alon’s second eigenvalue conjecture and related problems
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
- Complete Minors in Graphs Without Sparse Cuts
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Correction to: ``Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
- Cycle lengths in expanding graphs
- Eigenvalues and perfect matchings
- Expander graphs and their applications
- Expanders -- how to find them, and what to find in them
- Handbook of satisfiability. In 2 parts
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 2174386 (Why is no real title available?)
- scientific article; zbMATH DE number 2086404 (Why is no real title available?)
- scientific article; zbMATH DE number 2087215 (Why is no real title available?)
- scientific article; zbMATH DE number 871922 (Why is no real title available?)
- scientific article; zbMATH DE number 7788347 (Why is no real title available?)
- Isoperimetric numbers of graphs
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Locality and hard SAT-instances
- Lower bounds for the polynomial calculus
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Lower bounds on the size of semidefinite programming relaxations
- On Small-depth Frege Proofs for Tseitin for Grids
- On the odd-minor variant of Hadwiger's conjecture
- On the width of semialgebraic proofs and algorithms
- On Tseitin formulas, read-once branching programs and treewidth
- Optimality of size-degree tradeoffs for polynomial calculus
- Paths, Trees, and Flowers
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- Probability and Computing
- Proof Complexity
- Pseudorandom Generators in Propositional Proof Complexity
- Random graphs.
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- Sum of squares bounds for the ordering principle
- Sum of squares lower bounds for refuting any CSP
- Sum of squares lower bounds from symmetry and a good story
- Sum-of-squares Lower Bounds for Planted Clique
- Sum-of-squares proofs and the quest toward optimal algorithms
- The matching problem has no small symmetric SDP
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The relation between polynomial calculus, Sherali-Adams, and sum-of-squares proofs
- The relative efficiency of propositional proof systems
- The threshold for SDP-refutation of random regular NAE-3SAT
- Towards an understanding of polynomial calculus: new separations and lower bounds (extended abstract)
- TWO THEOREMS IN GRAPH THEORY
Cited in
(4)
This page was built for publication: Perfect matching in random graphs is as hard as Tseitin
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6562700)
