NP-hardness of Coloring 2-Colorable Hypergraph with Poly-logarithmically Many Colors
September 12, 2018 (GHC 6115)

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.