Sub-optimality of Local Algorithms on Sparse Random Graphs

This thesis studies local algorithms for solving combinatorial optimization problems on large, sparse random graphs. Local algorithms are randomized algorithms that run in parallel at each vertex of a graph by using only local information around each vertex. They produce important structures on large graphs such as independent sets, matchings, colourings and eigenfunctions of the graph Laplacian with only constant running time and little memory usage. Hatami, Lovasz and Szegedy conjectured that all reasonable optimization problems on large random d-regular graphs can be approximately solved by local algorithms. This is true for matchings: local algorithms can produce near perfect matchings in random d-regular graphs. However, this conjecture was recently shown to be false for independent sets by Gamarnik and Sudan. They showed that local algorithms cannot generate maximal independent sets on large random d-regular graphs if the degree d is sufficiently large. We prove an optimal rate of failure of this conjecture for the problem of percolation on graphs. The basic question is this. Consider a large integer T, which we consider a threshold parameter. Given some large graph G, find the maximum sized induced subgraph of G whose connected components have size no bigger than T. When T equals 1 this is the problem of finding the maximum independent sets in G. We show that for asymptotically large values of the degree d, local algorithms cannot solve the percolation problem on random d-regular graphs and Erdos-Renyi graphs of expected average degree d. Roughly speaking, we prove that the largest induced subgraph with a given threshold that local algorithms can find is no more than half of the maximum possible size. This is optimal because there exists local algorithms that can find such induced subgraphs of half the maximum size. Part of this thesis represents joint work with Balint Virag.Ph.D