ECCC-Report TR14-043https://eccc.weizmann.ac.il/report/2014/043Comments and Revisions published for TR14-043en-usThu, 03 Apr 2014 16:50:43 +0300
Paper TR14-043
| Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs |
Euiwoong Lee,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2014/043Consider 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.Thu, 03 Apr 2014 16:50:43 +0300https://eccc.weizmann.ac.il/report/2014/043