Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions

Girish Varma

In a recent result, Khot and Saket [FOCS 2014] proved the quasi-NP-hardness of coloring a 2-colorable 12-uniform hypergraph with $2^{(\log n{)}^{\Omega (1)}}$ colors. This result was prove…