$2^{(\log N{)}^{1/10-o(1)}}$ Hardness for Hypergraph Coloring

Sangxia Huang

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N{)}^{1/10-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus o…