Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
From MaRDI portal
Publication:2968154
DOI10.1137/15100240XzbMath1359.68109MaRDI QIDQ2968154
Publication date: 10 March 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ A Characterization of hard-to-cover CSPs ⋮ Hardness of Rainbow Coloring Hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The hardness of 3-uniform hypergraph coloring
- Improved low-degree testing and its applications
- Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
- Improved Hardness of Approximating Chromatic Number
- New approximation guarantee for chromatic number
- Coloring 3-colorable graphs with o(n 1/5 ) colors
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
- Hardness of Approximate Hypergraph Coloring
- Making the Long Code Shorter
- Conditional Hardness for Approximate Coloring
- Hardness results for approximate hypergraph coloring
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Improving the performance guarantee for approximate graph coloring
- Approximate graph coloring by semidefinite programming
- New approximation algorithms for graph coloring
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Coloring bipartite hypergraphs
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Optimal Testing of Reed-Muller Codes
- Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
- Some optimal inapproximability results
- Approximation resistance from pairwise independent subgroups
- On the hardness of approximating the chromatic number
