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 k 2 , given a Q k -uniform hypergraph which admits a k -rainbow coloring satisfying the following condition:

--- in each hyperedge e , for some e all but 2 e colors occur exactly Q times and the rest ( Q 1 ) times,

it is NP-hard to compute an independent set of (1 − ( + 1 ) k + ) -fraction of vertices, for any constant 0"> 0 . In particular, this implies the hardness of even ( k ) -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 (1) -coloring 2 -colorable 4 -uniform hypergraphs due to Saket, and k -rainbow colorable 2 k -uniform hypergraphs due to Guruswami and Lee.