Theory Lunch Seminar

Tuesday, September 11, 2018 - 12:00pm to 1:00pm

Location:

ASA Conference Room 6115 Gates Hillman Centers

Speaker:

AMEY BHANGALE, Post-Doctoral Fellow http://paul.rutgers.edu/~arb182/

NP-hardness of Coloring 2-Colorable Hypergraph with Poly-logarithmically Many Colors


Speaker: Amey Bhangale

Location: ASA Conference Room 6115


NP-hardness of Coloring 2-Colorable Hypergraph with Poly-logarithmically Many Colors

The best known polynomial time algorithms to color a 2-colorable hypergraph require a polynomial (in the number of vertices) number of colors. The hardness results for hypergraphs with lower uniformity are far from the known upper bounds.

In this talk, I will present short and simple proofs of the following results: Given a 2-colorable 4-uniform hypergraph on n vertices,

  1. It is NP-hard to color it with (log n)^c colors for some c>0.
  2. It is quasi-NP-hard to color it with O( (log n)^{1−o(1)}) colors.

In terms of NP-hardness, it improves the result of Guruswami, H{\aa}stad and Sudan, combined with Moshkovitz-Raz, by an `exponential' factor. The second result improves the result of Saket by a large polynomial factor. Furthermore, (1) is the first to show the NP-hardness of coloring a c-colorable k-uniform hypergraph with poly-logarithmically many colors, for any constants c>=2 and k>=3.

CMU Theory YouTube Channel

Event Website:

http://www.cs.cmu.edu/~theorylunch/abstractsHTML/September%2012,%202018.html

For More Information, Contact:

Keywords:

Seminar Series