 Main
Replica Symmetry Breaking in the Random Regular kNAESAT Problem
 Bartha, Zsolt
 Advisor(s): Ganguly, Shirshendu
Abstract
For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. For random ksat and related models it happens at constraint (clause) density α = αsat ≍ 2^k, where α is the number of constraints per variable. Just below the threshold, further results suggest that the solution space has a ”one step replica symmetry breaking” (1rsb) structure of a large bounded number of nearorthogonal clusters inside {0, 1}^N .
In the unsatisfiable regime α > αsat, it is natural to consider the problem of maxsatisfiability: violating the least number of constraints. This is a combinatorial optimization problem on the random energy landscape defined by the problem instance. For a simplified variant, the strong refutation problem, there is strong evidence that an algorithmic transition occurs around α = N^{k/2−1}. For α bounded in N, a very precise estimate of the maxsat value was obtained by Achlioptas, Naor, and Peres (2007), but it is not sharp enough to indicate the nature of the energy landscape. Later work (Sen, 2016; Panchenko, 2016) shows that for α very large (roughly, Ω(64k)) the maxsat value approaches the meanfield (complete graph) limit: this is conjectured to have a ”full replica symmetry breaking” (frsb) structure where nearoptimal configurations form clusters within clusters, in an ultrametric hierarchy of infinite depth inside {0, 1}^N . A stronger form of frsb was shown in several recent works to have algorithmic implications (again, in complete graphs). Consequently we find it of interest to understand how the model transitions from 1rsb near αsat, to (conjecturally) frsb for large α. In this work we show that in the random regular knaesat model, the 1rsb description breaks down already above α ≍ 4^k/k^3. This is proved by an explicit perturbation in the 2rsb parameter space. The choice of perturbation is inspired by the “bug proliferation” mechanism proposed by physicists (Montanari and RicciTersenghi, 2003; Krzakala, Pagnani, and Weigt, 2004), corresponding roughly to a percolationlike threshold for a subgraph of dependent variables.
Main Content
Enter the password to open this PDF file:













