Hardness of Rainbow Coloring Hypergraphs
From MaRDI portal
Publication:5136325
DOI10.4230/LIPIcs.FSTTCS.2017.33zbMath1491.68144OpenAlexW2788053798MaRDI QIDQ5136325
Rishi Saket, Venkatesan Guruswami
Publication date: 25 November 2020
Full work available at URL: http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs2017.html#GuruswamiS17
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)
Related Items (3)
On the structure of the set of panchromatic colorings of a random hypergraph ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
Cites Work
- 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 3-uniform hypergraph coloring
- On reverse hypercontractivity
- Gaussian bounds for noise correlation of functions
- Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
- New approximation guarantee for 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
- Cover-Decomposition and Polychromatic Numbers
- Hardness of Approximate Hypergraph Coloring
- Proof verification and the hardness of approximation problems
- Constructive Discrepancy Minimization by Walking on the Edges
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
- On the power of unique 2-prover 1-round games
- Improving the performance guarantee for approximate graph coloring
- Probabilistic checking of proofs
- Approximate graph coloring by semidefinite programming
- New approximation algorithms for graph coloring
- Approximate hypergraph coloring
- A Parallel Repetition Theorem
- Coloring bipartite hypergraphs
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Coloring -colorable graphs using relatively small palettes
- The Quest for Strong Inapproximability Results with Perfect Completeness
- Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
- $(2+\varepsilon)$-Sat Is NP-hard
- Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
- Some optimal inapproximability results
- On the hardness of approximating the chromatic number
This page was built for publication: Hardness of Rainbow Coloring Hypergraphs
