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.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 2
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 4
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2015
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif)
Licensed under a Creative Commons Attribution License