Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-051 | 12th April 2014 17:18

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2^{(\log n)^{\Omega(1)}} Colors

RSS-Feed




TR14-051
Authors: Subhash Khot, Rishi Saket
Publication: 12th April 2014 19:10
Downloads: 3444
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint