Limits of local algorithms for randomly generated constraint satisfaction problems

A major challenge in the field of random graphs is constructing fast algorithms for solving a variety of combinatorial optimization problems, such as finding largest independent set of a graph or finding a satisfying assignment in random instances of K-SAT problem. Most of the algorithms that have been successfully analyzed in the past are so-called local algorithms which rely on making decisions based on local information.
In this talk we will discuss fundamental barrier on the power of local algorithms to solve such problems, despite the conjectures put forward in the past. In particular, we refute a conjecture regarding the power of local algorithms to find nearly largest independent sets in random regular graphs. Similarly, we show that a broad class of local algorithms, including the so-called Belief Propagation and Survey Propagation algorithms, cannot find satisfying assignments in random NAE-K-SAT problem above a certain asymptotic threshold, below which even simple algorithms succeed with high probability. Our negative results exploit fascinating geometry of feasible solutions of random constraint satisfaction problems, which was first predicted by physicists heuristically and now confirmed by rigorous methods. According to this picture, the solution space exhibits a clustering property whereby the feasible solutions tend to cluster according to the underlying Hamming distance. We show that success of local algorithms would imply violation of such a clustering property thus leading to a contradiction.
Joint work with Madhu Sudan (Microsoft Research).