Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe threshold for SDP-refutation of random regular NAE-3SAT
98
0
0.0
(
0
)
Added by
Tselil Schramm
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 $d geq 8$, 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).
rate research
Read More
We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, ``two-eigenvalue 2CSPs. We show this SDP value coincides with the spectral relaxation value, possibly indicating a computational threshold. Our analysis extends the previously resolved cases of random regular $mathsf{2XOR}$ and $textsf{NAE-3SAT}$, and includes new cases such as random $mathsf{Sort}_4$ (equivalently, $mathsf{CHSH}$) and $mathsf{Forrelation}$ CSPs. Our techniques include new generalizations of the nonbacktracking operator, the Ihara--Bass Formula, and the Friedman/Bordenave proof of Alons Conjecture.
We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~${pm 1}^n$. For each model $mathcal{M}$, we identify the high-probability value~$s^*_{mathcal{M}}$ of the natural SDP relaxation (equivalently, the quantum value). That is, for all $varepsilon > 0$ we show that the SDP optimum of a random $n$-variable instance is (when normalized by~$n$) in the range $(s^*_{mathcal{M}}-varepsilon, s^*_{mathcal{M}}+varepsilon)$ with high probability. Our class of models includes non-regular CSPs, and ones where the SDP relaxation value is strictly smaller than the spectral relaxation value.
Recent work has made substantial progress in understanding the transitions of random constraint satisfaction problems. In particular, for several of these models, the exact satisfiability threshold has been rigorously determined, confirming predictions of statistical physics. Here we revisit one of these models, random regular k-NAE-SAT: knowing the satisfiability threshold, it is natural to study, in the satisfiable regime, the number of solutions in a typical instance. We prove here that these solutions have a well-defined free energy (limiting exponential growth rate), with explicit value matching the one-step replica symmetry breaking prediction. The proof develops new techniques for analyzing a certain survey propagation model associated to this problem. We believe that these methods may be applicable in a wide class of related problems.
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/n ge widetilde O(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/n ge widetilde O(n^{(k/2-1)(1-delta)})$ in time $exp(widetilde O(n^{delta}))$ or in $widetilde O(n^{delta})$ rounds of the sum-of-squares hierarchy, for any $delta in [0,1)$ and any integer $k ge 3$. 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.
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the density, for which a precise landscape of predictions has been made via statistical physics-based heuristics. In parallel, there has been a recent flurry of work on refuting random constraint satisfaction problems, via nailing refutation thresholds for spectral and semidefinite programming-based algorithms, and also on counting solutions to CSPs. Inspired by this, the starting point for our work is the following question: what does the solution space for a random CSP look like to an efficient algorithm? In pursuit of this inquiry, we focus on the following problems about random Boolean CSPs at the densities where they are unsatisfiable but no refutation algorithm is known. 1. Counts. For every Boolean CSP we give algorithms that with high probability certify a subexponential upper bound on the number of solutions. We also give algorithms to certify a bound on the number of large cuts in a Gaussian-weighted graph, and the number of large independent sets in a random $d$-regular graph. 2. Clusters. For Boolean $3$CSPs we give algorithms that with high probability certify an upper bound on the number of clusters of solutions. 3. Balance. We also give algorithms that with high probability certify that there are no unbalanced solutions, i.e., solutions where the fraction of $+1$s deviates significantly from $50%$. Finally, we also provide hardness evidence suggesting that our algorithms for counting are optimal.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
