Chicago Journal of Theoretical Computer Science

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


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.

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

DOI: 10.4086/cjtcs.2015.003

[] Article 2 [] Article 4
[back] Volume 2015 [back] Published articles
[CJCTS home]