@inproceedings{25fa8f1ec18d4713a41fcba63d39a3a2,
title = "Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(logn}ω(1) colors",
abstract = "We show that it is quasi-NP-hard to color 2-colorable 12-uniform hypergraphs with 2(logn}ω(1) colors where n is the number of vertices. Previously, Guruswami et al. [1] showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with 22ω &root;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.",
keywords = "Coloring, Hypergraph, Inapproximability, PCP",
author = "Subhash Khot and Rishi Saket",
note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 ; Conference date: 18-10-2014 Through 21-10-2014",
year = "2014",
month = dec,
day = "7",
doi = "10.1109/FOCS.2014.30",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "206--215",
booktitle = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
}