Hardness of rainbow coloring hypergraphs
From MaRDI portal
Publication:5136325
Recommendations
- Rainbow coloring hardness via low sensitivity polymorphisms
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
Cites work
- A Parallel Repetition Theorem
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Approximate graph coloring by semidefinite programming
- Approximate hypergraph coloring
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Coloring -colorable graphs using relatively small palettes
- Coloring bipartite hypergraphs
- Constructive discrepancy minimization by walking on the edges
- Gaussian bounds for noise correlation of functions
- Hardness of Approximate Hypergraph Coloring
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs
- Improving the performance guarantee for approximate graph coloring
- New approximation algorithms for graph coloring
- New approximation guarantee for chromatic number
- On reverse hypercontractivity
- On the Hardness of 4-Coloring a 3-Colorable Graph
- On the hardness of approximating the chromatic number
- On the power of unique 2-prover 1-round games
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions
- Some optimal inapproximability results
- Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
- The hardness of 3-uniform hypergraph coloring
- The quest for strong inapproximability results with perfect completeness
- Tight hardness results for minimizing discrepancy
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
- \((2+\varepsilon)\)-Sat is NP-hard
Cited in
(5)- On the structure of the set of panchromatic colorings of a random hypergraph
- Rainbow coloring hardness via low sensitivity polymorphisms
- Approximate hypergraph coloring under low-discrepancy and related promises
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
This page was built for publication: Hardness of rainbow coloring hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136325)
