Abstract
Consider a K-uniform hypergraph H = (V, E). A coloring c: V → {1, 2, …, 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 algorithmnds 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 ϵ, for any ϵ > 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.
One of our main technical tools is based on reverse hypercontractivity. Roughly, it says the noise operator increases q-norm of a function when q < 1, which is enough for some special cases of our results. To prove the full results, we generalize the reverse hypercontractivity to more general operators, which might be of independent interest. Together with the generalized reverse hypercontractivity and recent developments in inapproximability based on invariance principles for correlated spaces, we give a recipe for converting a promising test distribution and a suitable choice of an outer PCP to hardness of nding 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 rst analytic proof of (K − 1 − ϵ)-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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon, P. Kelsen, S. Mahajan and R. Hariharan: Approximate hypergraph coloring, Nordic Journal of Computing 3 (1996), 425–439.
P. Austrin, V. Guruswami and J. HÅstad: (2+ϵ)-SAT is NP-hard, in: Proceedings of the 55th annual symposium on Foundations of Computer Science, FOCS ’14, 1–10, 2014.
N. Bansal: Constructive algorithms for discrepancy minimization, in: Proceedings of the 51st annual IEEE symposium on Foundations of Computer Science, FOCS ’10, 3–10. IEEE, 2010.
N. Bansal and S. Khot: Inapproximability of hypergraph vertex cover and applications to scheduling problems, in: Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP ’10, 250–261, 2010.
B. Bollobás, D. Pritchard, T. Rothvoss and A. Scott: Cover-decomposition and polychromatic numbers, SIAM Journal on Discrete Mathematics 27 (2013), 240–256.
S. O. Chan: Approximation resistance from pairwise independent subgroups, in: Proceedings of the 45th annual ACM Symposium on Theory of Computing, STOC ’13, 447–456, 2013.
M. Charikar, A. Newman and A. Nikolov: Tight hardness results for minimizing discrepancy, in: Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms, 1607–1614, 2011.
H. Chen and A. M. Frieze: Coloring bipartite hypergraphs, in: Proceedings of the 5th international conference on Integer Programming and Combinatorial Optimization, IPCO 96, 345–358, 1996.
I. Dinur and V. Guruswami: PCPs via low-degree long code and hardness for constrained hypergraph coloring, in: Proceedings of the 54th annual symposium on Foundations of Computer Science, FOCS 13, 340–349, 2013.
I. Dinur, V. Guruswami, S. Khot and O. Regev: A new multilayered PCP and the hardness of hypergraph vertex cover, SIAM Journal on Computing 34 (2005), 1129–1146.
I. Dinur, E. Mossel and O. Regev: Conditional hardness for approximate coloring, SIAM Journal on Computing 39 (2009), 843–873.
I. Dinur, O. Regev and C. D. Smyth: The hardness of 3-Uniform hypergraph coloring, Combinatorica 25 (2005), 519–535.
P. Gopalan, S. Khot and R. Saket: Hardness of reconstructing multivariate polynomials over nite elds, SIAM Journal on Computing 39 (2010), 2598–2621.
V. Guruswami, J. Håstad, P. Harsha, S. Srinivasan and G. Varma: Super-polylogarithmic hypergraph coloring hardness via low-degree long codes, in: Proceedings of the 46th annual ACM Symposium on Theory of Computing, STOC ’14, 2014.
V. Guruswami, J. Håstad and M. Sudan: Hardness of approximate hypergraph coloring, SIAM Journal on Computing 31 (2002), 1663–1686.
J. Håstad: On the NP-hardness of Max-Not-2, SIAM Journal on Computing 49 (2014), 179–193.
G. H. Hardy, J. E. Littlewood and G. Pólya: Inequalities, Cambridge university press, 1952.
J. Holmerin: Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-ϵ, in: Proceedings of the 34th annual ACM Symposium on Theory of Computing, STOC ’02, 544–552, 2002.
S. Huang: Approximation resistance on satisable instances for predicates with few accepting inputs, in: Proceedings of the 45th annual ACM symposium on Symposium on Theory of Computing, STOC ’13, 457–466, 2013.
S. Khot: Hardness results for coloring 3-colorable 3-uniform hypergraphs, in: Proceedings of the 43rd annual IEEE symposium on Foundations of Computer Science, FOCS ’02, 23–32. IEEE, 2002.
S. Khot and R. Saket: Hardness of nding independent sets in 2-colorable and almost 2-colorable hypergraphs, in: Proceedings of the 25th annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, 1607–1625, 2014.
S. Lovett and R. Meka: Constructive discrepancy minimization by walking on the edges, in: Proceedings of the 53rd annual IEEE symposium on Foundations of Computer Science, FOCS 12, 61–67, 2012.
E. Mossel: Gaussian bounds for noise correlation of functions, Geometric and Functional Analysis 19 (2010), 1713–1756.
E. Mossel, R. O’Donnell, O. Regev, J. E. Steif and B. Sudakov: Non-interactive correlation distillation, inhomogeneous markov chains, and the reverse bonami-beckner inequality, Israel Journal of Mathematics 154 (2006), 299–336.
E. Mossel, K. Oleszkiewicz and A. Sen: On reverse hypercontractivity, Geometric and Functional Analysis 23 (2013), 1062–1097.
R. O’Donnell: Analysis of Boolean Functions, Cambridge University Press, 2014.
R. O’Donnell and Y. Wu: Conditional hardness for satisable 3-CSPs, in: Pro-ceedings of the 41st annual ACM Symposium on Theory of Computing, STOC ’09, 493–502, 2009.
S. Sachdeva and R. Saket: Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover, in: Proceedings of the 28th annual IEEE Conference on Computational Complexity, CCC ’13, 219–229, 2013.
R. Saket: Hardness of nding independent sets in 2-colorable hypergraphs and of satisable CSPs, in: Proceedings of the 29th annual IEEE Conference on Computational Complexity, CCC ’14, 78–89, 2014.
A. Samorodnitsky and L. Trevisan: Gowers uniformity, in uence of variables, and PCPs, SIAM Journal on Computing 39 (2009), 323–360.
C. Wenner: Circumventing d-to-1 for approximation resistance of satisable predicates strictly containing parity of width four, Theory of Computing 9 (2013), 703–757.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported in part by NSF grant CCF-1115525. Most of this work was done while visiting Microsoft Research New England.
Supported by a Samsung Fellowship, US-Israel BSF grant 2008293, and NSF CCF-1115525. Most of this work was done while visiting Microsoft Research New England.
Rights and permissions
About this article
Cite this article
Guruswami, V., Lee, E. Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Combinatorica 38, 547–599 (2018). https://doi.org/10.1007/s00493-016-3383-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-016-3383-0