Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$

by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan

Theory of Computing, Volume 18(3), pp. 1-29, 2022

Bibliography with links to cited articles

[1]   Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. [doi:10.1007/s00037-009-0272-6]

[2]   Boaz Barak, Pravesh K. Kothari, and David Steurer: Small-set expansion in shortcode graph and the 2-to-2 conjecture. In Proc. 10th Innovations in Theoret. Comp. Sci. conf. (ITCS’19), pp. 9:1–12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.9]

[3]   Aline Bonami: √Čtude des coefficients Fourier des fonctions de Lp(G). Ann. Inst. Fourier, 20(2):335–402, 1970. EuDML.

[4]   Siu On Chan: Approximation resistance from pairwise-independent subgroups. J. ACM, 63(3):27:1–32, 2016. [doi:10.1145/2873054]

[5]   Moses Charikar, MohammadTaghi Hajiaghayi, and Howard Karloff: Improved approximation algorithms for Label Cover problems. Algorithmica, 61(1):190–206, 2011. [doi:10.1007/s00453-010-9464-3]

[6]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms, 5(3):32:1–14, 2009. [doi:10.1145/1541885.1541893]

[7]   Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan: On weighted vs unweighted versions of combinatorial optimization problems. Inform. Comput., 167(1):10–26, 2001. Preliminary version in ISTCS’96. [doi:10.1006/inco.2000.3011]

[8]   Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra: Towards a proof of the 2-to-1 Games Conjecture? In Proc. 50th STOC, pp. 376–389. ACM Press, 2018. [doi:10.1145/3188745.3188804]

[9]   Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra: On non-optimally expanding sets in Grassmann graphs. Israel J. Math., 243:377–420, 2021. Preliminary version in STOC’18. [doi:10.1007/s11856-021-2164-7]

[10]   Lars Engebretsen: The nonapproximability of non-Boolean predicates. SIAM J. Discr. Math., 18(1):114–129, 2004. [doi:10.1137/S0895480100380458]

[11]   Lars Engebretsen and Jonas Holmerin: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Struct. Algor., 33(4):497–514, 2008. [doi:10.1002/rsa.20226]

[12]   Gil Goldshlager and Dana Moshkovitz: Approximating kCSP for large alphabets. Preprint, 2015. Available at author’s website.

[13]    Venkatesan Guruswami and Prasad Raghavendra: Constraint satisfaction over a non-Boolean domain: Approximation algorithms and Unique-Games hardness. In Proc. 11th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’08), pp. 77–90. Springer, 2008. [doi:10.1007/978-3-540-85363-3_7]

[14]   Gustav Hast: Approximating Max kCSP – outperforming a random assignment with almost a linear factor. In Proc. 32nd Internat. Colloq. on Automata, Languages, and Programming (ICALP’05), pp. 956–968. Springer, 2005. [doi:10.1007/11523468_77]

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

[16]   Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. [doi:10.1137/S0097539705447372]

[17]   Subhash Khot, Dor Minzer, and Muli Safra: Pseudorandom sets in Grassmann graph have near-perfect expansion. In Proc. 59th FOCS, pp. 592–601. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00062]

[18]   Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ϵ. J. Comput. System Sci., 74(3):335–349, 2008. [doi:10.1016/j.jcss.2007.06.019]

[19]   Subhash Khot and Rishi Saket: Approximating CSPs using LP relaxation. In Proc. 42nd Internat. Colloq. on Automata, Languages, and Programming (ICALP’15), pp. 822–833. Springer, 2015. [doi:10.1007/978-3-662-47672-7_67]

[20]   Guy Kindler, Alexandra Kolla, and Luca Trevisan: Approximation of non-Boolean 2CSP. In Proc. 27th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’16), pp. 1705–1714. SIAM, 2016. [doi:10.1137/1.9781611974331.ch117]

[21]   Konstantin Makarychev and Yury Makarychev: Approximation algorithm for non-Boolean Max-k-CSP. Theory of Computing, 10(13):341–358, 2014. [doi:10.4086/toc.2014.v010a013]

[22]   Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan: Near-optimal UGC-hardness of approximating Max k-CSPR. In Proc. 19th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’16), pp. 15:1–28. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.APPROX-RANDOM.2016.15]

[23]   Elchanan Mossel: Gaussian bounds for noise correlation of functions and tight analysis of long codes. In Proc. 49th FOCS. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.44]

[24]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: Invariance and optimality. Ann. Math., 171(1):295–341, 2010. [doi:10.4007/annals.2010.171.295]

[25]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. CUP.

[26]   Alex Samorodnitsky and Luca Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2000. [doi:10.1145/335305.335329]

[27]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. SIAM J. Comput., 39(1):323–360, 2009. Preliminary version in STOC’06. [doi:10.1137/070681612]

[28]   Luca Trevisan: Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72–88, 1998. [doi:10.1007/PL00009209]