### Volume 2015

#### Article 3

Published by the Department of Computer Science, The University of Chicago.

#### Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions

Girish Varma
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, INDIA
girish AT geevi DOT github DOT io

July 26, 2015

#### Abstract

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 proved using a novel outer PCP verifier which had a strong soundness guarantee. We reduce the arity in their result by modifying their 12-query inner verifier to an 8-query inner verifier based on the hypergraph coloring hardness reductions of Guruswami et al [STOC 2014]. More precisely, we prove quasi-NP-hardness of the following problems on $n$-vertex hypergraphs.
• Coloring a $2$-colorable $8$-uniform hypergraph with $2^{(\log n)^{\Omega(1)}}$ colors.
• Coloring a $4$-colorable $4$-uniform hypergraph with $2^{(\log n)^{\Omega(1)}}$ colors.

• The article: PDF (207 KB)
• Source material: ZIP (197 KB)
• BibTeX entry for this article (287 bytes)

Submitted November 14, 2014, revised June 1, 2015, and in final form July 23, 2015, published July 26, 2015.

Article 2 Article 4
Volume 2015 Published articles