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]