The threshold for SDP-refutation of random regular NAE-3SAT

DOI10.1137/1.9781611975482.140MaRDI QIDQ5236327zbMATH OpenOpenAlexFDO

Authors Yash Deshpande, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen, Andrea Montanari

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the property that spectral/SDP algorithms can efficiently refute random instances when the constraint density is a large constant (with high probability). But do these methods work immediately above the "satisfiability threshold", or is there still a range of constraint densities for which random NAE-3SAT instances are unsatisfiable but hard to refute? We show that the latter situation prevails, at least in the context of random regular instances and SDP-based refutation. More precisely, whereas a random $d$-regular instance of NAE-3SAT is easily shown to be unsatisfiable (whp) once $dgeq8$, we establish the following sharp threshold result regarding efficient refutation: If $d<13.5$ then the basic SDP, even augmented with triangle inequalities, fails to refute satisfiability (whp), if $d>13.5$ then even the most basic spectral algorithm refutes satisfiability~(whp).

Recommendations

• Satisfiability threshold for random regular NAE-SAT
• Satisfiability threshold for random regular \textsc{nae-sat}
• Strongly refuting random CSPs below the spectral threshold
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Lower bounds for CSP refutation by SDP hierarchies

Cited in

(7)

• A spectral condition for spectral gap: fast mixing in high-temperature Ising models
• Lower bounds for CSP refutation by SDP hierarchies
• Constructing concrete hard instances of the maximum independent set problem
• Explicit Near-Ramanujan Graphs of Every Degree
• Spectral gap in random bipartite biregular graphs and applications
• Perfect matching in random graphs is as hard as Tseitin
• Extreme singular values of inhomogeneous sparse random rectangular matrices

This page was built for publication: The threshold for SDP-refutation of random regular NAE-3SAT

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