Conditional Hardness for Approximate Coloring
From MaRDI portal
Publication:3575151
DOI10.1137/07068062XzbMATH Open1192.68317OpenAlexW2047861934MaRDI QIDQ3575151FDOQ3575151
Authors: Irit Dinur, Elchanan Mossel, 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
Recommendations
- Conditional hardness for approximate coloring
- Hardness of Approximate Hypergraph Coloring
- Complexity of conditional colorability of graphs
- On the hardness of approximating the chromatic number
- Complexity of conditional colourings with given template
- Two generalizations of proper coloring: hardness and approximability
- Hardness and inapproximability of convex recoloring problems
- Approximating the Interval Constrained Coloring Problem
- Approximate hypergraph coloring
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (40)
- Title not available (Why is that?)
- Deciding Relaxed Two-Colourability: A Hardness Jump
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Simultaneous max-cut is harder to approximate than max-cut
- Title not available (Why is that?)
- On percolation and ‐hardness
- Hypergraph list coloring and Euclidean Ramsey theory
- Two generalizations of proper coloring: hardness and approximability
- Approximately coloring graphs without long induced paths
- Bounds on 2-query locally testable codes with affine tests
- Title not available (Why is that?)
- Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems
- Query-efficient dictatorship testing with perfect completeness
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- The Quest for Strong Inapproximability Results with Perfect Completeness
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover
- Topology and Adjunction in Promise Constraint Satisfaction
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
- Robust Factorizations and Colorings of Tensor Graphs
- Linear Index Coding via Semidefinite Programming
- Title not available (Why is that?)
- Bi-Covering: Covering Edges with Two Small Subsets of Vertices
- High dimensional Hoffman bound and applications in extremal combinatorics
- Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
- Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
- Kneser graphs are like Swiss cheese
- Coloring tournaments with few colors: algorithms and complexity
- Approximate graph colouring and the hollow shadow
- Title not available (Why is that?)
- Title not available (Why is that?)
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
- Title not available (Why is that?)
This page was built for publication: Conditional Hardness for Approximate Coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575151)
