Conditional hardness for approximate coloring
From MaRDI portal
Publication:2931398
DOI10.1145/1132516.1132567zbMath1301.68143arXivcs/0504062OpenAlexW2004804919MaRDI QIDQ2931398
Irit Dinur, Elchanan Mossel, Oded Regev
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0504062
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A note on unique games, Gaussian bounds for noise correlation of functions, A quantitative Arrow theorem, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Maximally stable Gaussian partitions with discrete applications, Noise stability of functions with low influences: invariance and optimality, A simple algorithm for 4-coloring 3-colorable planar graphs, On the tractability of coloring semirandom graphs, Robust optimality of Gaussian noise stability, Unnamed Item, New Tools for Graph Coloring