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