Hardness results for approximate hypergraph coloring

DOI10.1145/509907.509962MaRDI QIDQ3579207zbMATH OpenOpenAlexFDO

Authors Subhash Khot

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/509907.509962

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cited in

(4)

• NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• Three‐query PCPs with perfect completeness over non‐Boolean domains

This page was built for publication: Hardness results for approximate hypergraph coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579207)