Sum of squares lower bounds for refuting any CSP

DOI10.1145/3055399.3055485MaRDI QIDQ4977967zbMATH OpenOpenAlexFDO

Authors Pravesh Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsconstraint satisfactionsum-of-squares semidefinite programming hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: Let $P:{0,1}^{k}o0,1$ be a nontrivial $k$-ary predicate. Consider a random instance of the constraint satisfaction problem $mathrmCSP(P)$ on $n$ variables with $Deltan$ constraints, each being $P$ applied to $k$ randomly chosen literals. Provided the constraint density satisfies $Deltagg1$, such an instance is unsatisfiable with high probability. The emph{refutation} problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate $P$ supports a $t$-emph{wise uniform} probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree $d=Theta(fracnDelt{a}^{2/(t-1)}logDelta)$ (which runs in time $n^{O(d)}$) emph{cannot} refute a random instance of $mathrmCSP(P)$. In particular, the polynomial-time SOS algorithm requires $widetildeOmega(n^{(t+1)/2})$ constraints to refute random instances of CSP$(P)$ when $P$ supports a $t$-wise uniform distribution on its satisfying assignments. Together with recent work of Lee et al. [LRS15], our result also implies that emph{any} polynomial-size semidefinite programming relaxation for refutation requires at least $widetildeOmega(n^{(t+1)/2})$ constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate~$P$, they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen et al. [AOW15] and Raghavendra et al. [RRS16], this full three-way tradeoff is emph{tight}, up to lower-order factors.

Recommendations

• Lower bounds for CSP refutation by SDP hierarchies
• Strongly refuting random CSPs below the spectral threshold
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Tight size-degree bounds for sums-of-squares proofs
• Tight size-degree bounds for sums-of-squares proofs

Cited in

(41)

• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
• scientific article; zbMATH DE number 7559092 (Why is no real title available?)
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Algorithmic obstructions in the random number partitioning problem
• Sherali-adams strikes back
• Perfect matching in random graphs is as hard as Tseitin
• Strongly refuting random CSPs below the spectral threshold
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Sum-of-squares certificates for maxima of random tensors on the sphere
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Towards breaking the exponential barrier for general secret sharing
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Constructing concrete hard instances of the maximum independent set problem
• Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation?
• Max-3-Lin over non-abelian groups with universal factor graphs
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Sum of squares lower bounds from symmetry and a good story
• Computational barriers to estimation from low-degree polynomials
• Sum-of-squares bounds via Boolean function analysis
• Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• scientific article; zbMATH DE number 7378399 (Why is no real title available?)
• Indistinguishability obfuscation
• Sum of Squares Bounds for the Empty Integral Hull Problem
• Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
• Tight size-degree bounds for sums-of-squares proofs
• Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
• Tight size-degree bounds for sums-of-squares proofs
• Lower bounds for CSP refutation by SDP hierarchies
• A systematic study of sparse LWE
• Lossy cryptography from code-based assumptions
• Average-case complexity of tensor decomposition for low-degree polynomials
• Algorithms approaching the threshold for semi-random planted clique
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Sum-of-squares proofs and the quest toward optimal algorithms
• Sherali-Adams strikes back

This page was built for publication: Sum of squares lower bounds for refuting any CSP

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