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
• Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
• Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
• 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 (22)

• Title not available (Why is that?)
• Approximate coloring of uniform hypergraphs
• Title not available (Why is that?)
• Two generalizations of proper coloring: hardness and approximability
• On the hardness of approximating the chromatic number
• A Characterization of hard-to-cover CSPs
• 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
• The Quest for Strong Inapproximability Results with Perfect Completeness
• Hardness of Rainbow Coloring Hypergraphs
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• 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
• Conditional Hardness for Approximate Coloring
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
• Title not available (Why is that?)

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)