Towards a Characterization of Approximation Resistance for Symmetric CSPs

by Venkatesan Guruswami and Euiwoong Lee

Theory of Computing, Volume 13(3), pp. 1-24, 2017

Bibliography with links to cited articles

[1]   Per Austrin, Siavosh Benabbas, and Avner Magen: On quadratic threshold CSPs. Discr. Math. & Theoret. Comput. Sci., 14(2):205–228, 2012. Avilable at HAL. Preliminary version in LATIN’10.

[2]   Per Austrin and Johan Håstad: On the usefulness of predicates. ACM Trans. Comput. Theory, 5(1):1:1–1:24, 2013. Preliminary version in CCC’12. [doi:10.1145/2462896.2462897, arXiv:1204.5662]

[3]   Per Austrin and Subhash Khot: A characterization of approximation resistance for even k-partite CSPs. In Proc. 4th Conf. on Innovations in Theoret. Comput. Sci. (ITCS’13), pp. 187–196. ACM Press, 2013. [doi:10.1145/2422436.2422459, arXiv:1301.2731]

[4]   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]

[5]   Boaz Barak, Siu On Chan, and Pravesh K. Kothari: Sum of squares lower bounds from pairwise independence. In Proc. 47th STOC, pp. 97–106. ACM Press, 2015. [doi:10.1145/2746539.2746625, arXiv:1501.00734]

[6]   Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani: SDP gaps from pairwise independence. Theory of Computing, 8(12):269–289, 2012. [doi:10.4086/toc.2012.v008a012]

[7]   Siu On Chan: Approximation resistance from pairwise independent subgroups. J. ACM, 63(3):27:1–27:32, 2016. Preliminary versions in STOC’13 and ECCC. [doi:10.1145/2873054]

[8]   Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, and Ola Svensson: Approximating linear threshold predicates. ACM Trans. Comput. Theory, 4(1):2:1–2:31, 2012. Preliminary version in APPROX’10. [doi:10.1145/2141938.2141940]

[9]   Wing-Sum Cheung: Generalizations of Hölder’s inequality. Internat. J. Math.& Math. Sci., 26(1):7–10, 2001. [doi:10.1155/S0161171201005658]

[10]   Venkatesan Guruswami and Euiwoong Lee: Towards a characterization of approximation resistance for symmetric CSPs. In Proc. 18th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’15), pp. 305–322. Springer, 2015. Preliminary version at ECCC. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.305]

[11]   Gustav Hast: Beating a Random Assignment: Approximating Constraint Satisfaction Problems. Ph. D. thesis, KTH, Numerical Analysis and Computer Science, NADA, 2005. QC 20101020. Avaliable at DiVA.

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

[13]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. Also in CCC’02. [doi:10.1145/509907.510017]

[14]   Subhash Khot, Madhur Tulsiani, and Pratik Worah: A characterization of strong approximation resistance. In Proc. 46th STOC, pp. 634–643. ACM Press, 2014. [doi:10.1145/2591796.2591817, arXiv:1305.5500]

[15]   Thomas J. Schaefer: The complexity of satisfiability problems. In Proc. 10th STOC, pp. 216–226. ACM Press, 1978. [doi:10.1145/800133.804350]

[16]   Madhur Tulsiani: CSP gaps and reductions in the Lasserre hierarchy. In Proc. 41st STOC, pp. 303–312. ACM Press, 2009. [doi:10.1145/1536414.1536457]

[17]   Uri Zwick: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’98), pp. 201–210. ACM Press, 1998. ACM DL.