Hardness of Approximate Hypergraph Coloring

DOI10.1137/S0097539700377165MaRDI QIDQ3149889zbMATHDBLPWikidataFDO

Authors Venkatesan Guruswami, Johan Hastad, Madhu Sudan

Publication date 29 September 2002

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

zbMATH Keywords

graph coloringset splittinghypergraph coloringPCPhardness of approximationscovering PCP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The hardness of 3-uniform hypergraph coloring
• 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

Cited in

(21)

• Hardness of rainbow coloring hypergraphs
• An expected polynomial time algorithm for coloring 2-colorable 3-graphs
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• On the hardness of approximating the chromatic number
• Conditional Hardness for Approximate Coloring
• Privacy-preserving data splitting: a combinatorial approach
• Rainbow coloring hardness via low sensitivity polymorphisms
• scientific article; zbMATH DE number 7561683 (Why is no real title available?)
• A characterization of hard-to-cover CSPs
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• The quest for strong inapproximability results with perfect completeness
• Approximating the orthogonality dimension of graphs and hypergraphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A note on unique games
• A polynomial time algorithm for checking 2-chromaticity for recursively constructed \(k\)-terminal hypergraphs
• Approximate coloring of uniform hypergraphs
• Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions
• Two generalizations of proper coloring: hardness and approximability
• Function simulation, graph grammars and colourings
• NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors

This page was built for publication: Hardness of Approximate Hypergraph Coloring

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