Partly on the basis of heuristic arguments from physics, it has been suggested that the performance of certain types of algorithms on random @math -SAT formulas is linked to phase transitions that affect the geometry of the set of satisfying assignments. But, beyond intuition, there has been scant rigorous evidence that “practical” algorithms are affected by these phase transitions. In this paper we prove that Walksat, a popular randomized satisfiability algorithm, fails on random @math -SAT formulas not very far above clause variable density, where the set of satisfying assignments shatters into tiny, well-separated clusters. Specifically, we prove that Walksat is ineffective with high probability (w.h.p.) if @math , where @math is the number of clauses, @math is the number of variables, and @math is an absolute constant. By comparison, Walksat is known to find satisfying assignments in linear time w.h.p. if @math [A. Coja-Oghlan and A. Frieze, SIAM J. Comput., 43 (2...
Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research has shown that such algorithms show significant promise in computing structures like large independent sets in graphs locally. Indeed the promise led to a conjecture by Hatami, and Szegedy HatamiLovaszSzegedy that local algorithms may be able to compute maximum independent sets in (sparse) random @math -regular graphs. In this paper we refute this conjecture and show that every independent set produced by local algorithms is multiplicative factor @math smaller than the largest, asymptotically as @math . Our result is based on an important clustering phenomena predicted first in the literature on spin glasses, and recently proved rigorously for a variety of constraint satisfaction problems on random graphs. Such properties suggest that the geometry of the solution space can be quite intricate. The specific clustering property, that we prove and apply in this paper shows that typically every two large independent sets in a random graph either have a significant intersection, or have a nearly empty intersection. As a result, large independent sets are clustered according to the proximity to each other. While the clustering property was postulated earlier as an obstruction for the success of local algorithms, such as for example, the Belief Propagation algorithm, our result is the first one where the clustering property is used to formally prove limits on local algorithms. We show that the largest density of factor of i.i.d. independent sets in the dd-regular tree is asymptotically at most (logd) d(log⁡d) d as d→∞d→∞. This matches the lower bound given by previous constructions. It follows that the largest independent sets given by local algorithms on random dd-regular graphs have the same asymptotic density. In contrast, the density of the largest independent sets in these graphs is asymptotically 2(logd) d2(log⁡d) d. We prove analogous results for Poisson–Galton–Watson trees, which yield bounds for local algorithms on sparse Erdős–Renyi graphs. 