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

covering PCPgraph coloringhardness of approximationshypergraph coloringPCPset splitting

Mathematics Subject Classification ID

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

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)

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

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)