Sum-of-squares proofs and the quest toward optimal algorithms
From MaRDI portal
Publication:4589017
zbMATH Open1373.68253arXiv1404.5236MaRDI QIDQ4589017FDOQ4589017
Authors: Boaz Barak, David Steurer 
Publication date: 6 November 2017
Abstract: In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible guarantees for a wide range of different problems. The Unique Games Conjecture (UGC) is a tantalizing conjecture in computational complexity, which, if true, will shed light on the complexity of a great many problems. In particular this conjecture predicts that a single concrete algorithm provides optimal guarantees among all efficient algorithms for a large class of computational problems. The Sum-of-Squares (SOS) method is a general approach for solving systems of polynomial constraints. This approach is studied in several scientific disciplines, including real algebraic geometry, proof complexity, control theory, and mathematical programming, and has found applications in fields as diverse as quantum information theory, formal verification, game theory and many others. We survey some connections that were recently uncovered between the Unique Games Conjecture and the Sum-of-Squares method. In particular, we discuss new tools to rigorously bound the running time of the SOS method for obtaining approximate solutions to hard optimization problems, and how these tools give the potential for the sum-of-squares method to provide new guarantees for many problems of interest, and possibly to even refute the UGC.
Full work available at URL: https://arxiv.org/abs/1404.5236
Recommendations
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (39)
- Notes on computational-to-statistical gaps: predictions using statistical physics
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- On the bit complexity of sum-of-squares proofs
- Test sets for nonnegativity of polynomials invariant under a finite reflection group
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Approximability and proof complexity
- Perfect matching in random graphs is as hard as Tseitin
- Proof complexity and the binary encoding of combinatorial principles
- Limitations of semidefinite programs for separable states and entangled games
- The Lovász theta function for random regular graphs and community detection in the hard regime
- Sum-of-squares certificates for maxima of random tensors on the sphere
- Noisy tensor completion via the sum-of-squares hierarchy
- The Ising Antiferromagnet and Max Cut on Random Regular Graphs
- Bounds on the norms of uniform low degree graph matrices
- The moment-SOS hierarchy: applications and related topics
- The power of Sherali-Adams relaxations for general-valued CSPs
- The Lovász theta function for random regular graphs and community detection in the hard regime
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- Title not available (Why is that?)
- Tight size-degree bounds for sums-of-squares proofs
- A note on probably certifiably correct algorithms
- High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
- Algorithms approaching the threshold for semi-random planted clique
- NLTS Hamiltonians from good quantum codes
- An improved semidefinite programming hierarchy for testing entanglement
- Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
- Disordered systems insights on computational hardness
- SOS is not obviously automatizable, even approximately
- The Complexity of Public-Key Cryptography
- A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
- On space and depth in resolution
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum-of-squares hierarchies for binary polynomial optimization
- Rounding sum-of-squares relaxations
- On Flattenability of Graphs
- Hypercontractivity, sum-of-squares proofs, and their applications
- An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
This page was built for publication: Sum-of-squares proofs and the quest toward optimal algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589017)
