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 language | English (US) |
---|---|
Pages (from-to) | 235-271 |
Number of pages | 37 |
Journal | SIAM Journal on Computing |
Volume | 46 |
Issue number | 1 |
DOIs | |
State | Published - 2017 |
Keywords
- Coloring
- Hypergraph
- Inapproximability
- PCP
ASJC Scopus subject areas
- General Computer Science
- General Mathematics