Strongly refuting random CSPs below the spectral threshold

DOI10.1145/3055399.3055417MaRDI QIDQ4977966zbMATH OpenOpenAlexFDO

Authors

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/1605.00058

zbMATH Keywords

random constraint satisfaction problemsspectral algorithmsstrong refutationsum-of-squares hierarchy

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a value of $m=Omega(n)$ beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when $m/n=omega(1)$). Intuitively, strong refutation should become easier as the clause density $m/n$ grows, because the contradictions introduced by the random clauses become more locally apparent. For CSPs such as $k$-SAT and $k$-XOR, there is a long-standing gap between the clause density at which efficient strong refutation algorithms are known, $m/ngewidetildeO(n^{k/2-1})$, and the clause density at which instances become unsatisfiable with high probability, $m/n=omega(1)$. In this paper, we give spectral and sum-of-squares algorithms for strongly refuting random $k$-XOR instances with clause density $m/ngewidetildeO(n^{(k/2-1)(1-delta)})$ in time $exp(widetildeO(n^{delta}))$ or in $widetildeO(n^{delta})$ rounds of the sum-of-squares hierarchy, for any $deltain[0,1)$ and any integer $kge3$. Our algorithms provide a smooth transition between the clause density at which polynomial-time algorithms are known at $delta=0$, and brute-force refutation at the satisfiability threshold when $delta=1$. We also leverage our $k$-XOR results to obtain strong refutation algorithms for SAT (or any other Boolean CSP) at similar clause densities. Our algorithms match the known sum-of-squares lower bounds due to Grigoriev and Schonebeck, up to logarithmic factors. Additionally, we extend our techniques to give new results for certifying upper bounds on the injective tensor norm of random tensors.

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Sum of squares lower bounds for refuting any CSP
• Strong Refutation Heuristics for Random k-SAT
• Note on strong refutation algorithms for random \(k\)-SAT formulas
• Lower bounds for CSP refutation by SDP hierarchies

Cited in

(21)

• Towards breaking the exponential barrier for general secret sharing
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Noisy tensor completion via the sum-of-squares hierarchy
• Lower bounds for CSP refutation by SDP hierarchies
• Sum of squares lower bounds for refuting any CSP
• Improper learning by refuting
• Sum-of-squares certificates for maxima of random tensors on the sphere
• Disordered systems insights on computational hardness
• Sherali-adams strikes back
• Sherali-Adams strikes back
• The threshold for SDP-refutation of random regular NAE-3SAT
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
• Subexponential-time algorithms for sparse PCA
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Certifying Euclidean sections and finding planted sparse vectors beyond the \(\sqrt{n}\) dimension threshold
• The Kikuchi hierarchy and tensor PCA
• Improved search-to-decision reduction for random local functions
• Spectral refutations of semirandom k-LIN over larger fields

This page was built for publication: Strongly refuting random CSPs below the spectral threshold

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