Hardness results for approximate hypergraph coloring
From MaRDI portal
Publication:3579207
DOI10.1145/509907.509962zbMath1192.68325OpenAlexW2139689595MaRDI QIDQ3579207
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
Programming involving graphs or networks (90C35) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Three‐query PCPs with perfect completeness over non‐Boolean domains ⋮ PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Unnamed Item ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
This page was built for publication: Hardness results for approximate hypergraph coloring
