Hardness results for approximate hypergraph coloring

Research output: Contribution to journalConference articlepeer-review


Guruswami et al [6] show the hardness of coloring 2-colorable 4-uniform hypergraphs on n vertices with Ω(log log n/log log log n) colors assuming NP ⊈ DTIME(nO(log log n)). We obtain a stronger hardness result for approximate coloring of p-colorable 4-uniform hypergraphs for any fixed integer p ≥ 7. We prove that there exists an absolute constant c > 0 such that for every fixed integer p ≥ 7, it is hard to color a p-colorable 4-uniform hypergraph with (log n)cp colors assuming NP ⊈ DTIME(2(log n)O(1)). This work builds on the idea of "covering complexity" of probabilistically checkable proof systems (PCPs) developed in [6] and we introduce some new techniques as well. Firstly, we define a new code which we call the Split Code. This is a variation of the Long Code, but much shorter in length and it reduces the proof size significantly. Split Codes enable us to exploit the special structure of the "outer PCP verifier" constructed via Raz's Parallel Repetition Theorem [18]. Secondly, we make a novel use of the Split Codes over the domain GF(p) for a prime p. Working over non-boolean domain in fact makes our proof technically simpler than the proof of Guruswami at al [6].

Original languageEnglish (US)
Pages (from-to)351-359
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2002
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Hardness results for approximate hypergraph coloring'. Together they form a unique fingerprint.

Cite this