SDP gaps from pairwise independence

DOI10.4086/TOC.2012.V008A012MaRDI QIDQ2913812zbMATH OpenOpenAlexFDO

Authors Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2012.v008a012

zbMATH Keywords

constraint satisfactionintegrality gapslinear programming hierarchiessemidefinite programming hierarchiespromising predicate

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Optimal Sherali-Adams Gaps from Pairwise Independence
• Approximation resistant predicates from pairwise independence
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Approximation Resistance from Pairwise-Independent Subgroups
• Approximation resistance from pairwise independent subgroups

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An explicit equivalent positive semidefinite program for nonlinear 0-1 programs

Cited in

(14)

• Optimal Sherali-Adams Gaps from Pairwise Independence
• On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
• From weak to strong linear programming gaps for all constraint satisfaction problems
• On the usefulness of predicates
• Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
• Cryptographic hardness of random local functions. Survey
• Approximation resistant predicates from pairwise independence
• On approximability of satisfiable k-CSPs: V
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Lower bounds for CSP refutation by SDP hierarchies
• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
• A comprehensive analysis of polyhedral lift-and-project methods
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Rank bounds for a hierarchy of Lovász and Schrijver

This page was built for publication: SDP gaps from pairwise independence

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