Skip to main content.
Advanced search >
<< Back to previous page Print

<< Wednesday, October 17, 2018 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


The Lovász theta function for random regular graphs

Seminar: Probability 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.


sganguly@berkeley.edu