Conditional Hardness for Approximate Coloring
From MaRDI portal
Publication:3575151
DOI10.1137/07068062XzbMath1192.68317OpenAlexW2047861934MaRDI QIDQ3575151
Elchanan Mossel, Irit Dinur, Oded Regev
Publication date: 7 July 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/07068062x
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Topology and Adjunction in Promise Constraint Satisfaction, Bounds on 2-query locally testable codes with affine tests, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Unnamed Item, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank, Pseudorandom sets in Grassmann graph have near-perfect expansion, Bi-Covering: Covering Edges with Two Small Subsets of Vertices, Unnamed Item, Robust Factorizations and Colorings of Tensor Graphs, 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, High dimensional Hoffman bound and applications in extremal combinatorics, Unnamed Item, On percolation and ‐hardness, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Kneser graphs are like Swiss cheese, Linear Index Coding via Semidefinite Programming, Query-Efficient Dictatorship Testing with Perfect Completeness, Unnamed Item, Approximately coloring graphs without long induced paths, Unnamed Item, Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Hypergraph list coloring and Euclidean Ramsey theory, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, Simultaneous max-cut is harder to approximate than max-cut, The Quest for Strong Inapproximability Results with Perfect Completeness, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Unnamed Item, Unnamed Item, Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}), Finding Pseudorandom Colorings of Pseudorandom Graphs