Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe number of solutions for random regular NAE-SAT
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We consider the sum of two large Hermitian matrices $A$ and $B$ with a Haar unitary conjugation bringing them into a general relative position. We prove that the eigenvalue density on the scale slightly above the local eigenvalue spacing is asymptotically given by the free convolution of the laws of $A$ and $B$ as the dimension of the matrix increases. This implies optimal rigidity of the eigenvalues and optimal rate of convergence in Voiculescus theorem. Our previous works [3,4] established these results in the bulk spectrum, the current paper completely settles the problem at the spectral edges provided they have the typical square-root behavior. The key element of our proof is to compensate the deterioration of the stability of the subordination equations by sharp error estimates that properly account for the local density near the edge. Our results also hold if the Haar unitary matrix is replaced by the Haar orthogonal matrix.
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).
MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size $k$, for some $kge 2$. We refer to this problem as MAX NAE-${k}$-SAT. For $k=2$, it is essentially the celebrated MAX CUT problem. For $k=3$, it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For $kge 4$, it is known that an approximation ratio of $1-frac{1}{2^{k-1}}$, obtained by choosing a random assignment, is optimal, assuming $P e NP$. For every $kge 2$, an approximation ratio of at least $frac{7}{8}$ can be obtained for MAX NAE-${k}$-SAT. There was some hope, therefore, that there is also a $frac{7}{8}$-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no $frac{7}{8}$-approximation algorithm for MAX NAE-SAT, assuming the unique games conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-${3,5}$-SAT (i.e., MAX NAE-SAT where all clauses have size $3$ or $5$), the best approximation ratio that can be achieved, assuming UGC, is at most $frac{3(sqrt{21}-4)}{2}approx 0.8739$. Using calculus of variations, we extend the analysis of ODonnell and Wu for MAX CUT to MAX NAE-${3}$-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-${3}$-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is $approx 0.9089$. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-${3,5}$-SAT with a conjectured approximation ratio of 0.8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0.8698.
Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $dgeq3$. We prove that, with probability $1-N^{-1+{varepsilon}}$ for any ${varepsilon} >0$, the following two properties hold as $N to infty$ provided that $dgeq3$: (i) The eigenvalues are close to the classical eigenvalue locations given by the Kesten-McKay distribution. In particular, the extremal eigenvalues are concentrated with polynomial error bound in $N$, i.e. $lambda_2, |lambda_N|leq 2+N^{-c}$. (ii) All eigenvectors of random $d$-regular graphs are completely delocalized.
We show that throughout the satisfiable phase the normalised number of satisfying assignments of a random $2$-SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to `true under a uniformly random satisfying assignment.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
