文章基本信息

标题：Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions
本地全文：下载
作者：Girish Varma
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2015
卷号：2015
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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.