Combinatorial Optimization Reading Group - Joshua NevinExport this event to calendar

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

Title: Approximate Coloring of 2-Colorable 4-Uniform Hypergraphs

Speaker: Joshua Nevin
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

In this talk, we discuss several inapproximability results of Bhangale for 2-colorable 4-uniform hypergraphs. These results provide the best known lower bounds, under certain assumptions, on the number of colors which must be used in the worst case by a polynomial-time algorithm providing an explicit coloring of a 4-uniform hypergraph which is known to be 2-colorable. In particular, we show that no such algorithm can use at most polylogarithmically many colors (polylogarithmic in the number of vertices), assuming that P is not equal to NP. This result extends to an analogous result for c-colorable k-uniform hypergraphs, for any c>1 and k>2.

Location 
MC - Mathematics & Computer Building
5501
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 (141)
    1. October (12)
    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)