Inside the clustering window for random linear equations
arXiv:1512.06657
Abstract
We study a random system of cn linear equations over n variables in GF(2), where each equation contains exactly r variables; this is equivalent to r-XORSAT. Previous work has established a clustering threshold, c^*_r for this model: if c=c_r^*-εfor any constant ε>0 then with high probability all solutions form a well-connected cluster; whereas if c=c^*_r+ε, then with high probability the solutions partition into well-connected, well-separated clusters (with probability tending to 1 as n goes to infinity). This is part of a general clustering phenomenon which is hypothesized to arise in most of the commonly studied models of random constraint satisfaction problems, via sophisticated but mostly non-rigorous techniques from statistical physics. We extend that study to the range c=c^*_r+o(1), and prove that the connectivity parameters of the r-XORSAT clusters undergo a smooth transition around the clustering threshold.
arXiv comment25 pages. A major part of this paper has appeared in the preprint arXiv:1309.6651
References in corpus (9)
- Clustering of solutions in the random satisfiability problem
- Coloring random graphs
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- On the freezing of variables in random constraint satisfaction problems
- A better algorithm for random k-SAT
- Catching the k-NAESAT Threshold
- The Satisfiability Threshold for k-XORSAT
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
- The stripping process can be slow: part I