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)1∕10-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]