Hardness of Coloring -Colorable -Uniform Hypergraphs with Colors
In the authors' words
We show that it is quasi-NP-hard to color a -colorable -uniform hypergraph on vertices using colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a -colorable -uniform hypergraph on vertices using colors.
Main resultThe abstract does not state a limitation.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 20 pages