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

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

Cited in

(5)

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

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)