Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma · 2014
We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the"short code" of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.