Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions
Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions
复制标题
降低 Khot-Saket 超图着色硬度降低的均匀性
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
G. Varma
中科院分区：
文献类型：
--
作者：
G. Varma
在最近的结果中，Khot和Saket [Focs 2014]证明了为2颜色的12-均匀超图涂上$ 2^{（log n）^{omega（1）}} $颜色的准清晰度。使用新型的外部PCP验证仪证明了这一结果，该验证器具有强大的合理性保证。在本说明中，我们表明，我们可以根据Guruswami等的超图形性硬度降低，将其12次质量内部验证器修改为8质量内部验证器，从而降低其结果的影响。 al。 [Stoc 2014]。更确切地说，我们证明了N-Vertex HyperGraphs上以下问题的准NP硬度。
- 用$ 2^{（log n）^{omega（1）}} $颜色着色2色8-均匀的超图。
- 为$ 2^{（log n）^{Omega（1）}} $颜色着色4色4均匀的超图。
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. In this note, we show that we can reduce the arity of 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.