Conditional hardness for approximate coloring
From MaRDI portal
Publication:2931398
DOI10.1145/1132516.1132567zbMath1301.68143arXivcs/0504062MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, A note on unique games, 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, Maximally stable Gaussian partitions with discrete applications, A quantitative Arrow theorem, Robust optimality of Gaussian noise stability, Gaussian bounds for noise correlation of functions, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), New Tools for Graph Coloring