The Lovász theta function for random regular graphs

Seminar | October 17 | 3-4 p.m. | 1011 Evans Hall

 Jess Banks, UC Berkeley

 Department of Statistics

The Lovász theta function is a classic semidefinite relaxation of graph coloring. In this talk I'll discuss the power of this relaxation for refuting colorability of uniformly random degree-regular graphs, as well as for distinguishing this distribution from one with a `planted' disassoratative community structure. We will see that the behavior of this refutation scheme is consistent with the conjecture that coloring and community detection exhibit a `computationally hard but information-theoretically feasible' regime typical of random constraint satisfaction and statistical inference problems. The proofs will make use of orthogonal polynomials, nonbacktracking walks, and results on the spectra of random regular graphs.