Sub-optimality of local algorithms for some problems on sparse random graphs

Combinatorics Seminar
Friday, December 1, 2017 - 15:00
1 hour (actually 50 minutes)
Skiles 005
Suppose we want to find the largest independent set or maximal cut in a sparse Erdos-Renyi graph, where the average degree is constant. Many algorithms proceed by way of local decision rules, for instance, the "nibbling" procedure. I will explain a form of local algorithms that captures many of these. I will then explain how these fail to find optimal independent sets or cuts once the average degree of the graph gets large. There are some nice connections to entropy and spin glasses.