Hardness of rainbow coloring hypergraphs
DOI10.4230/LIPICS.FSTTCS.2017.33zbMATH Open1491.68144OpenAlexW2788053798MaRDI QIDQ5136325FDOQ5136325
Venkatesan Guruswami, Rishi Saket
Publication date: 25 November 2020
Full work available at URL: http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs2017.html#GuruswamiS17
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
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Boolean functions (06E30)
Cites Work
- Approximate graph coloring by semidefinite programming
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Some optimal inapproximability results
- Gaussian bounds for noise correlation of functions
- On the power of unique 2-prover 1-round games
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Improving the performance guarantee for approximate graph coloring
- New approximation algorithms for graph coloring
- Cover-Decomposition and Polychromatic Numbers
- A Parallel Repetition Theorem
- New approximation guarantee for chromatic number
- Title not available (Why is that?)
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
- On reverse hypercontractivity
- Coloring -colorable graphs using relatively small palettes
- The hardness of 3-uniform hypergraph coloring
- Constructive Discrepancy Minimization by Walking on the Edges
- Coloring bipartite hypergraphs
- Hardness of Approximate Hypergraph Coloring
- On the hardness of approximating the chromatic number
- 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
- Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring
- On the Hardness of 4-Coloring a 3-Colorable Graph
- $(2+\varepsilon)$-Sat Is NP-hard
- Title not available (Why is that?)
- Approximate hypergraph coloring
- The Quest for Strong Inapproximability Results with Perfect Completeness
- Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
Cited In (3)
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)
