Approximability and proof complexity
From MaRDI portal
Abstract: This work is concerned with the proof-complexity of certifying that optimization problems do emph{not} have good solutions. Specifically we consider bounded-degree "Sum of Squares" (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof system is automatizable using semidefinite programming (SDP), meaning that any -variable degree- proof can be found in time . Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the "-round Lasserre value" of an optimization problem is equal to the best bound provable using a degree- SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known "hard instances" for the Unique-Games problem are in fact solved close to optimally by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot--Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 () using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?
Recommendations
Cited in
(27)- Sum-of-squares rank upper bounds for matching problems
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- Tight size-degree bounds for sums-of-squares proofs
- Lift-and-project methods for set cover and knapsack
- Efficient algorithms for privately releasing marginals via convex relaxations
- Quantum de Finetti theorems under local measurements with applications
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- Proof Complexity and the Kneser-Lovász Theorem
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Approximation and Small-Depth Frege Proofs
- scientific article; zbMATH DE number 1206797 (Why is no real title available?)
- Communication lower bounds via critical block sensitivity
- Sum-of-squares proofs and the quest toward optimal algorithms
- Tight size-degree bounds for sums-of-squares proofs
- SOS is not obviously automatizable, even approximately
- Complexity Approximation Principle
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- On the bit complexity of sum-of-squares proofs
- The Complexity of Somewhat Approximation Resistant Predicates
- Majority is stablest: discrete and SoS
- scientific article; zbMATH DE number 2212170 (Why is no real title available?)
- Majority is stablest: discrete and SoS
- scientific article; zbMATH DE number 7753415 (Why is no real title available?)
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- First-order reasoning and efficient semi-algebraic proofs
- Certifying Euclidean sections and finding planted sparse vectors beyond the \(\sqrt{n}\) dimension threshold
This page was built for publication: Approximability and proof complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741820)
