Rounding Semidefinite Programming Hierarchies via Global Correlation

DOI10.1109/FOCS.2011.95zbMath1292.90226MaRDI QIDQ5495026

Boaz Barak, Prasad Raghavendra, David Steurer

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Making the Long Code Shorter ⋮ On Flattenability of Graphs ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ A faster interior-point method for sum-of-squares optimization ⋮ A unified view of graph regularity via matrix decompositions ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Graph Clustering using Effective Resistance ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Product-state approximations to quantum states ⋮ Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks ⋮ Lift-and-project methods for set cover and knapsack ⋮ New Tools for Graph Coloring ⋮ Sherali-adams strikes back ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lasserre integrality gaps for graph spanners and related problems