Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs

DOI10.1137/1.9781611973402.117zbMath1423.68193arXiv1308.3247OpenAlexW2949537674MaRDI QIDQ5384079

Subhash A. Khot, Rishi Saket

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.3247

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Unnamed Item ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Unnamed Item ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Hardness of Rainbow Coloring Hypergraphs

This page was built for publication: Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs