Sum-of-squares proofs and the quest toward optimal algorithms
From MaRDI portal
Publication:4589017
zbMath1373.68253arXiv1404.5236MaRDI QIDQ4589017
Publication date: 6 November 2017
Full work available at URL: https://arxiv.org/abs/1404.5236
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (27)
On space and depth in resolution ⋮ On Flattenability of Graphs ⋮ SOS Is Not Obviously Automatizable, Even Approximately ⋮ Disordered systems insights on computational hardness ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Tight size-degree bounds for sums-of-squares proofs ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ A note on probably certifiably correct algorithms ⋮ Unnamed Item ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Unnamed Item ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Limitations of semidefinite programs for separable states and entangled games ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ An improved semidefinite programming hierarchy for testing entanglement ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ The Complexity of Public-Key Cryptography ⋮ Test sets for nonnegativity of polynomials invariant under a finite reflection group
This page was built for publication: Sum-of-squares proofs and the quest toward optimal algorithms
