Sum of squares lower bounds from pairwise independence (extended abstract)

DOI10.1145/2746539.2746625MaRDI QIDQ2941493zbMATH OpenOpenAlexFDO

Authors Boaz Barak, Siu On Chan, Pravesh Kothari

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.00734

zbMATH Keywords

lower boundsconstraint satisfactionpairwise independencesum of squares hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We prove that for every $epsilon>0$ and predicate $P:{0,1}^{k}ightarrow0,1$ that supports a pairwise independent distribution, there exists an instance $mathcalI$ of the $mathsfMaxP$ constraint satisfaction problem on $n$ variables such that no assignment can satisfy more than a $frac|P^{-1}(1)|2^k+epsilon$ fraction of $mathcalI$'s constraints but the degree $Omega(n)$ Sum of Squares semidefinite programming hierarchy cannot certify that $mathcalI$ is unsatisfiable. Similar results were previously only known for weaker hierarchies.

Recommendations

• SDP gaps from pairwise independence
• Sum of squares lower bounds for refuting any CSP
• Optimal Sherali-Adams Gaps from Pairwise Independence
• Approximation resistant predicates from pairwise independence
• Approximation Resistance from Pairwise-Independent Subgroups

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(14)

• A nearly tight sum-of-squares lower bound for the planted clique problem
• scientific article; zbMATH DE number 7559092 (Why is no real title available?)
• Sum of squares lower bounds for refuting any CSP
• Optimal Sherali-Adams Gaps from Pairwise Independence
• SDP gaps from pairwise independence
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
• Sum of squares lower bounds from symmetry and a good story
• Tight Probability Bounds with Pairwise Independence
• On the hardest problem formulations for the 0/1 Lasserre hierarchy
• Cryptographic hardness of random local functions. Survey
• An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
• A Lasserre lower bound for the min-sum single machine scheduling problem
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Sum of squares lower bounds from pairwise independence (extended abstract)

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