Collins Conference Room
Seminar
  US Mountain Time
Speaker: 
Jess Banks (University of California, Berkeley)

Our campus is closed to the public for this event.

Abstract.  The Sum-of-Squares (SOS) hierarchy is a powerful family of semidefinite programming relaxations which, in some cases, has produced the fastest known algorithms for NP-complete problems. We study the problem of deciding whether a randomly chosen degree-regular graph is colorable with k colors, and in particular when second round of the SOS hierarchy can verify that such a graph is not colorable. Using recent results from the spectral theory of random regular graphs, as well as a surprising connection to orthogonal polynomials, we show that with high probability, the threshold at which degree-two SOS can refute k-colorability of a d-regular graph is asymptotically k = 1 + d/2(d-1)^1/2.

Purpose: 
Research Collaboration
SFI Host: 
Josh Grochow

More SFI Events