Hardness of Approximate Hypergraph Coloring

DOI10.1137/S0097539700377165zbMath1008.68052DBLPjournals/siamcomp/GuruswamiHS02WikidataQ56958987 ScholiaQ56958987MaRDI QIDQ3149889

Venkatesan Guruswami, Johan T. Håstad

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)

Related Items (17)

A note on unique games ⋮ PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ A Characterization of hard-to-cover CSPs ⋮ Vertex cover might be hard to approximate to within \(2 - \varepsilon \) ⋮ Unnamed Item ⋮ Privacy-preserving data splitting: a combinatorial approach ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ An expected polynomial time algorithm for coloring 2-colorable 3-graphs ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Function simulation, graph grammars and colourings ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Hardness of Rainbow Coloring Hypergraphs

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