Pages that link to "Item:Q4589017"

The following pages link to Sum-of-squares proofs and the quest toward optimal algorithms (Q4589017):

Displaying 33 items.

• Test sets for nonnegativity of polynomials invariant under a finite reflection group (Q258157) (← links)
• An improved semidefinite programming hierarchy for testing entanglement (Q529619) (← links)
• On space and depth in resolution (Q1616620) (← links)
• Tight size-degree bounds for sums-of-squares proofs (Q1686838) (← links)
• A note on probably certifiably correct algorithms (Q1695210) (← links)
• Notes on computational-to-statistical gaps: predictions using statistical physics (Q1729830) (← links)
• Limitations of semidefinite programs for separable states and entangled games (Q1731116) (← links)
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio (Q2103494) (← links)
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials (Q2143214) (← links)
• Noisy tensor completion via the sum-of-squares hierarchy (Q2144539) (← links)
• Sum-of-squares hierarchy lower bounds for symmetric formulations (Q2191774) (← links)
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian (Q2235162) (← links)
• High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts (Q2401179) (← links)
• On Flattenability of Graphs (Q3452282) (← links)
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem (Q4634034) (← links)
• SOS Is Not Obviously Automatizable, Even Approximately (Q4638114) (← links)
• Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors (Q4943883) (← links)
• The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime (Q5002631) (← links)
• Sum-of-squares certificates for maxima of random tensors on the sphere (Q5002634) (← links)
• (Q5005186) (← links)
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut (Q5009512) (← links)
• The Complexity of Public-Key Cryptography (Q5021130) (← links)
• Disordered systems insights on computational hardness (Q5055432) (← links)
• An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture (Q5120487) (← links)
• The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime (Q5232321) (← links)
• The Power of Sherali--Adams Relaxations for General-Valued CSPs (Q5348454) (← links)
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs (Q5864219) (← links)
• Sum-of-squares hierarchies for binary polynomial optimization (Q5918420) (← links)
• Sum-of-squares hierarchies for binary polynomial optimization (Q5925640) (← links)
• The Spectrum of the Grigoriev–Laurent Pseudomoments (Q6187076) (← links)
• Perfect matching in random graphs is as hard as Tseitin (Q6562700) (← links)
• Proof complexity and the binary encoding of combinatorial principles (Q6562831) (← links)
• The moment-SOS hierarchy: applications and related topics (Q6598421) (← links)