Sum of squares lower bounds for refuting any CSP

DOI10.1145/3055399.3055485zbMATH Open1370.68134arXiv1701.04521OpenAlexW2574497079MaRDI QIDQ4977967FDOQ4977967

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)

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.

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

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

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)

Cited In (41)

• Title not available (Why is that?)
• Algorithmic obstructions in the random number partitioning problem
• 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
• Perfect matching in random graphs is as hard as Tseitin
• Sherali-adams strikes back
• 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
• Title not available (Why is that?)
• 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
• Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN
• Sum-of-squares bounds via Boolean function analysis
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
• Tight size-degree bounds for sums-of-squares proofs
• 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
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials

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)