ECCC-Report TR14-051https://eccc.weizmann.ac.il/report/2014/051Comments and Revisions published for TR14-051en-usSat, 12 Apr 2014 19:10:06 +0300
Paper TR14-051
| Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors |
Subhash Khot,
Rishi Saket
https://eccc.weizmann.ac.il/report/2014/051We show that it is quasi-NP-hard to color $2$-colorable $12$-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color $2$-colorable $8$-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a standard Outer PCP with an Inner PCP based on the Short Code of super-constant degree. Our result is instead obtained by composing a new Outer PCP with an Inner PCP based on the Short Code of degree two.Sat, 12 Apr 2014 19:10:06 +0300https://eccc.weizmann.ac.il/report/2014/051