Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(logn}ω(1) colors

Subhash Khot, Rishi Saket

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PublisherIEEE Computer Society
Pages206-215
Number of pages10
ISBN (Electronic)9781479965175
DOIs
StatePublished - Dec 7 2014
Event55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States
Duration: Oct 18 2014Oct 21 2014

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
CountryUnited States
CityPhiladelphia
Period10/18/1410/21/14

Keywords

  • Coloring
  • Hypergraph
  • Inapproximability
  • PCP

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Hardness of coloring 2-colorable 12-uniform hypergraphs with 2<sup>(logn}ω(1)</sup> colors'. Together they form a unique fingerprint.

Cite this