Combinatorial Optimization Seminar - Julian Romero BarbosaExport this event to calendar

Friday, March 29, 2019 — 1:00 PM EDT

Title: Using Lasserre Hierarchy for Graph Coloring  

Speaker: Julian Romero Barbosa
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

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 find (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.

Location 
MC - Mathematics & Computer Building
5479
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)