ﻻ يوجد ملخص باللغة العربية
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).
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 i
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 relaxatio
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 predictio
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
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