The Lovász theta function for random regular graphs

Probability Seminar
Oct 17, 2018 3:00pm to 4:00pm
Location: 
1011 Evans Hall
Status: 
Happening As Scheduled
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...
Jess Banks, UC Berkeley