### 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,

- It is NP-hard to color it with (log n)^c colors for some c>0.
- 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.