CSP gaps and reductions in the lasserre hierarchy
From MaRDI portal
Publication:5172724
DOI10.1145/1536414.1536457zbMath1304.90157OpenAlexW2002025272MaRDI QIDQ5172724
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1536414.1536457
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (31)
Fair Colorful k-Center Clustering ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Tight size-degree bounds for sums-of-squares proofs ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Proof Complexity Meets Algebra ⋮ Affine reductions for LPs and SDPs ⋮ Limitations of semidefinite programs for separable states and entangled games ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Unnamed Item ⋮ Convex Relaxations and Integrality Gaps ⋮ Strong reductions for extended formulations ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lasserre integrality gaps for graph spanners and related problems ⋮ Fair colorful \(k\)-center clustering
This page was built for publication: CSP gaps and reductions in the lasserre hierarchy
