2026-07-24T03:00:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8390 2024-03-06T10:41:59Z ddc:004 open_access

Hardness of Rainbow Coloring Hypergraphs Guruswami, Venkatesan Saket, Rishi Fourier analysis of Boolean functions hypergraph coloring Inapproximability Label Cover PCP A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be nearly balanced rainbow colorable. Specifically, we show that for any Q,k >= 2 and \ell <= k/2, given a Qk-uniform hypergraph which admits a k-rainbow coloring satisfying: - in each hyperedge e, for some \ell_e <= \ell all but 2\ell_e colors occur exactly Q times and the rest (Q +/- 1) times, it is NP-hard to compute an independent set of (1 - (\ell+1)/k + \eps)-fraction of vertices, for any constant \eps > 0. In particular, this implies the hardness of even (k/\ell)-rainbow coloring such hypergraphs. The result is based on a novel long code PCP test that ensures the strong balancedness property desired of the k-rainbow coloring in the completeness case. The soundness analysis relies on a mixing bound based on uniform reverse hypercontractivity due to Mossel, Oleszkiewicz, and Sen, which was also used in earlier proofs of the hardness of \omega(1)-coloring 2-colorable 4-uniform hypergraphs due to Saket, and k-rainbow colorable 2k-uniform hypergraphs due to Guruswami and Lee. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan Guruswami and Rishi Saket 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.33 urn:nbn:de:0030-drops-83905 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.33 eng https://creativecommons.org/licenses/by/3.0/legalcode