Title: Using Lasserre Hierarchy for Graph Coloring
|Speaker:||Julian Romero Barbosa|
|Affiliation:||University of Waterloo|
In this talk, I will go over a technique introduced by Arora and Ge for coloring 3-colorable graphs having low threshold rank (i.e., graphs with few eigenvalues below certain negative constant). For regular graphs on n vertices, such techniques allow us to ﬁnd (with constant probability) an
independent set of size at least n/12 in time nO(D) where D is the threshold rank of the graph. If in addition, the graph is vertex-transitive, this implies that a coloring with O(log n) colors can be found in nO(d) time. A crucial ingredient in the proof is a neat interpretation of the solutions of the Lasserre Hierarchy relaxation as distributions over colorings of the graph. Informally speaking, when these distributions have a small ”variance”, it is possible to recover a large partial coloring of the graph, thus obtaining a large independent set. This is the case for graphs with low threshold rank.
200 University Avenue West
Waterloo, ON N2L 3G1