Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(log n)ω(1) colors

Subhash Khot, Rishi Saket

Research output: Contribution to journalArticlepeer-review

Abstract

We show that it is quasi-NP-hard to color 2-colorable 12-uniform hypergraphs with 2(log n)ω(1) colors where n is the number of vertices. Previously, Guruswami Harsha, Håstad, Srinivasan, and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with {equation presented} colors. Their result is obtained by composing a standard outer probabilistically checkable proof (PCP) with an inner PCP based on the short code of superconstant 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)
Pages (from-to)235-271
Number of pages37
JournalSIAM Journal on Computing
Volume46
Issue number1
DOIs
StatePublished - 2017

Keywords

  • Coloring
  • Hypergraph
  • Inapproximability
  • PCP

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(log n)ω(1) colors'. Together they form a unique fingerprint.

Cite this