Combinatorial Optimization Reading Group- Akshay RamachandranExport this event to calendar

Friday, March 8, 2019 — 1:00 PM EST

Title: On the Hardness of 4-coloring a 3-colorable graph

Speaker: Akshay Ramachandran
Affiliation: University of Waterloo
Room: MC 5479

Abstract: A consequence of the PCP theorem is that it is NP-hard to approximate the chromatic number of a general graph to within \n^{1-\eps} for any constant epsilon. On the other hand, we have seen results that allow us to color a 3-colorable graph with far fewer than n colors. In this talk we will discuss two constructions ([KLS20], [GK04]) that prove hardness of 4-coloring a 3-colorable graph. Both start from the hardness of approximating the clique number, but the former requires the PCP theorem, whereas the latter requires a much weaker hardness result. This will lead to a discussion of the relationship between inapproximability of coloring and PCP constructions: there are implications in both directions and so it is interesting to understand whether PCPs are intrinsic to these hardness results or artifacts of the current proof techniques.

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)