Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors

DOI10.1137/15100240XzbMath1359.68109MaRDI QIDQ2968154

Subhash A. Khot, Rishi Saket

Publication date: 10 March 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

inapproximability; hypergraph coloring; PCP

Mathematics Subject Classification ID

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)