Rounding Semidefinite Programming Hierarchies via Global Correlation

DOI10.1109/FOCS.2011.95MaRDI QIDQ5495026zbMATH OpenFDO

Authors 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)

Full work available at URL https://doi.org/10.1109/FOCS.2011.95

Mathematics Subject Classification ID

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

Cited in

(43)

• Lift-and-project methods for set cover and knapsack
• Lasserre integrality gaps for graph spanners and related problems
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
• Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
• New NP-hardness results for 3-coloring and 2-to-1 label cover
• On the hardest problem formulations for the 0/1 Lasserre hierarchy
• New tools for graph coloring
• 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
• Graph Clustering using Effective Resistance
• Approximating unique games using low diameter graph decomposition
• scientific article; zbMATH DE number 7378399 (Why is no real title available?)
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Sum-of-squares bounds via Boolean function analysis
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Sherali-adams strikes back
• Sherali-Adams strikes back
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Product-state approximations to quantum states
• Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks
• 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
• Algorithms approaching the threshold for semi-random planted clique
• Solving unique games over globally hypercontractive graphs
• A sublinear time tester for max-cut on clusterable graphs
• A spectral approach to approximately counting independent sets in dense bipartite graphs
• Improved combinatorial approximations for weighted correlation clustering
• Sparse cuts in hypergraphs from random walks on simplicial complexes
• Explicit SoS lower bounds from high-dimensional expanders
• SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
• Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
• Max-Cut with multiple cardinality constraints
• Sparsest cut and eigenvalue multiplicities on low degree abelian Cayley graphs
• Triangles improve 0.878 approximation for Maxcut
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number

This page was built for publication: Rounding Semidefinite Programming Hierarchies via Global Correlation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495026)