Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A simple polynomial-time algorithm finds a 2-coloring if $H$ admits a perfectly balanced rainbow $k$-coloring. For a hypergraph that admits an almost balanced rainbow coloring, we prove that it is NP-hard to find an independent set of size $\epsilon$, for any $\epsilon > 0$. Consequently, we cannot weakly color (avoiding monochromatic hyperedges) it with $O(1)$ colors. With $k = 2$, it implies strong hardness for discrepancy minimization of systems of bounded set-size.

Our techniques extend recent developments in inapproximability based on reverse hypercontractivity and invariance principles for correlated spaces. We give a recipe for converting a promising test distribution and a suitable choice of a outer PCP to hardness of finding an independent set in the presence of highly-structured colorings. We use this recipe to prove additional results almost in a black-box manner, including: (1) the first analytic proof of $(K-1-\epsilon)$-hardness of $K$-Hypergraph Vertex Cover with more structure in completeness, and (2) hardness of $(2Q+1)$-SAT when the input clause is promised to have an assignment where every clause has at least $Q$ true literals.