Hardness of Approximate Hypergraph Coloring

DOI10.1137/S0097539700377165MaRDI QIDQ3149889zbMATH OpenDBLPWikidataFDO

Authors Venkatesan Guruswami, Johan Hastad, Madhu Sudan

Publication date 29 September 2002

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

Full work available at URL https://doi.org/10.1137/S0097539700377165

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

(24)

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

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)