Abstract
I will consider two types of problems on large locally tree-like graphs:
(1) Finding a small subset of vertices that are better connected than the others; (2) Finding a small bisection. In the first case, I will prove that no local algorithm can solve the problem optimally, and instead a large gap exists between the optimum and the best solution that can be constructed locally. In the second case, I will provide evidence that --surprisingly--this gap vanishes. In particular, Glauber dynamics appears to approach the optimum with an arbitrary small error. Proving that this is indeed the case is an open problem.
Based on joint work with Song Mei