A Characterization of Hard-to-Cover CSPs

by Amey Bhangale, Prahladh Harsha, and Girish Varma

Theory of Computing, Volume 16(16), pp. 1-30, 2020

Bibliography with links to cited articles

[1]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Preliminary version in  FOCS’92. [doi:10.1145/278298.278306, ECCC:TR98-008]

[2]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in  FOCS’92. [doi:10.1145/273865.273901]

[3]   Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. Preliminary version in  CCC’08. [doi:10.1007/s00037-009-0272-6, arXiv:0802.2300, ECCC:TR08-009]

[4]   Nikhil Bansal and Subhash Khot: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proc. 37th Internat. Colloq. Automata, Lang., Programming (ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22]

[5]   Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer: Making the long code shorter. SIAM J. Comput., 44(5):1287–1324, 2015. Preliminary version in  FOCS’12. [doi:10.1137/130929394, arXiv:1111.0405, ECCC:TR11-142]

[6]    Amey Bhangale, Prahladh Harsha, and Girish Varma: A characterization of hard-to-cover CSPs. In Proc. 30th Comput. Complexity Conf. (CCC’15), pp. 280–303. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.CCC.2015.280, arXiv:1411.7747]

[7]   Irit Dinur and Venkatesan Guruswami: PCPs via the low-degree long code and hardness for constrained hypergraph coloring. Israel J. Math., 209:611–649, 2015. Preliminary version in  FOCS’13. [doi:10.1007/s11856-015-1231-3, ECCC:TR13-122]

[8]   Irit Dinur and Gillat Kol: Covering CSPs. In Proc. 28th IEEE Conf. on Comput. Complexity (CCC’13), pp. 207–218. IEEE Comp. Soc., 2013. [doi:10.1109/CCC.2013.29, ECCC:TR12-088]

[9]   Uriel Feige and Joe Kilian: Zero knowledge and the chromatic number. J. Comput. System Sci., 57(2):187–199, 1998. Preliminary version in  CCC’96. [doi:10.1006/jcss.1998.1587]

[10]   Venkat Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, and Girish Varma: Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. SIAM J. Comput., 46(1):132–159, 2017. Preliminary version in  STOC’14. [doi:10.1137/140995520, arXiv:1311.7407]

[11]   Venkatesan Guruswami, Johan Håstad, and Madhu Sudan: Hardness of approximate hypergraph coloring. SIAM J. Comput., 31(6):1663–1686, 2002. Preliminary version in  FOCS’00. [doi:10.1137/S0097539700377165]

[12]   Venkatesan Guruswami and Euiwoong Lee: Strong inapproximability results on balanced rainbow-colorable hypergraphs. Combinatorica, 38(3):547–599, 2018. Preliminary version in  SODA’15. [doi:10.1007/s00493-016-3383-0, ECCC:TR14-043]

[13]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in  STOC’97. [doi:10.1145/502090.502098]

[14]   Jonas Holmerin: Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ϵ. In Proc. 34th STOC, pp. 544–552. ACM Press, 2002. [doi:10.1145/509907.509986, ECCC:TR01-094]

[15]   Sangxia Huang: 2(log N)110-o(1) hardness for hypergraph coloring. 2015. [arXiv:1504.03923]

[16]   Subhash Khot and Rishi Saket: Hardness of coloring 2-colorable 12-uniform hypergraphs with 2(log n)Ω(1) colors. SIAM J. Comput., 46(1):235–271, 2017. Preliminary version in  FOCS’14. [doi:10.1137/15100240X, ECCC:TR14-051]

[17]   Michael Krivelevich, Ram Nathaniel, and Benny Sudakov: Approximating coloring and maximum independent sets in 3-uniform hypergraphs. J. Discr. Algor., 41(1):99–113, 2001. Preliminary version in  SODA’01. [doi:10.1006/jagm.2001.1173]

[18]   Elchanan Mossel: Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713–1756, 2010. Preliminary version in  FOCS’08. [doi:10.1007/s00039-010-0047-x, arXiv:math/0703683]

[19]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary version in  STOC’95. [doi:10.1137/S0097539795280895]

[20]   Rishi Saket: Hardness of finding independent sets in 2-colorable hypergraphs and of satisfiable CSPs. In Proc. 29th IEEE Conf. on Comput. Complexity (CCC’14), pp. 78–89. IEEE Comp. Soc., 2014. [doi:10.1109/CCC.2014.16, arXiv:1312.2915]

[21]   Girish Varma: Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. Chicago J. Theoret. Comp. Sci., (3):1–8, 2015. [doi:10.4086/cjtcs.2015.003, arXiv:1408.0262]

[22]   Cenny Wenner: Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Theory of Computing, 9(23):703–757, 2013. Preliminary version in  APPROX’12. [doi:10.4086/toc.2013.v009a023, ECCC:TR12-145]

[23]   David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6):103–128, 2007. Preliminary version in  STOC’06. [doi:10.4086/toc.2007.v003a006, ECCC:TR05-100]