Publication
FOCS 2014
Conference paper

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

View publication

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.

Date

Publication

FOCS 2014

Authors

Topics

Share