Hardness of Approximate Hypergraph Coloring
From MaRDI portal
Publication:3149889
DOI10.1137/S0097539700377165zbMath1008.68052WikidataQ56958987 ScholiaQ56958987MaRDI QIDQ3149889
Madhu Sudan, Venkatesan Guruswami, Johan T. Håstad
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
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
