Hardness of Approximate Hypergraph Coloring

DOI10.1137/S0097539700377165zbMATH Open1008.68052DBLPjournals/siamcomp/GuruswamiHS02WikidataQ56958987 ScholiaQ56958987MaRDI QIDQ3149889FDOQ3149889

Authors: Venkatesan Guruswami, Johan Hastad, Madhu Sudan 

Publication date: 29 September 2002

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

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

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)

Cited In (21)

• Title not available (Why is that?)
• Approximate coloring of uniform hypergraphs
• Two generalizations of proper coloring: hardness and approximability
• On the hardness of approximating the chromatic number
• A note on unique games
• 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
• Title not available (Why is that?)
• 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
• 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)