Departmental PhD Thesis Exam

Event Information Sub-optimality of local algorithms on sparse random graphs
11:10 on Wednesday May 06, 2015
12:00 on Wednesday May 06, 2015
BA6183, Bahen Center, 40 St. George St.
Mustazee Rahman
http://www.math.toronto.edu/~mustazee/Thesis.pdf
University of Toronto

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. In practice, they generate important structures on large graphs such as independent sets, matchings, colourings and eigenfunctions of the graph Laplacian with efficient run--time and little memory usage. They have also been used to solve instances of constraint satisfaction problems such as k-SAT.

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 quantitative measure of failure of this conjecture for the problem of percolation on graphs. The basic question is this. Consider a large integer T, which is 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 of G.

We show that for 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 for any given threshold the largest induced subgraphs that local algorithms can find have size no more than half of the maximal ones. This is optimal because there exist local algorithms that find such induced subgraphs of half the maximum size.

Part of this thesis represents joint work with Balint Virag.