Student Probability Seminar

---

Local Algorithms on Sparse Random Graphs

Speaker: Tim Kunisky, CIMS

Location: Warren Weaver Hall 512

Date: Wednesday, October 17, 2018, noon

Synopsis:

Imagine you want to solve an optimization problem on a graph, say finding the size of the largest independent set, or the largest cut. Local algorithms are a framework for approximating such quantities: place a little computer on every node of the graph, let it observe its neighborhood of some radius, and then have it decide—should its node belong to the independent set or not? Or, which side of the cut should its node belong to?

 

A recent line of work considers a special type of randomized local algorithm, where the little computers generate iid gaussians and aggregate them linearly over their neighborhoods. Tuning such algorithms over sparse random graphs reduces to studying certain gaussian processes on infinite trees, a perfectly respectable occupation even for those pure theorists allergic to little computers.

 

I will focus specifically on how this idea has been used to produce local algorithms approximating hard optimization problems on random d-regular graphs. The key will be to build special gaussian processes whose realizations look like extremal eigenfunctions of the infinite d-regular tree, and then to show that they may be approximated by gaussian local algorithms. If time permits, I will also mention the interesting story of how the random processes produced by such local algorithms arise naturally in ergodic theory.