Improved NP-Inapproximability for $2$-Variable Linear Equations

by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright

Theory of Computing, Volume 13(19), pp. 1-51, 2017

Bibliography with links to cited articles

[1]   Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev: O(√ ----
  logn) approximation algorithms for Min-Uncut, Min-2CNF-Deletion, and directed cut problems. In Proc. 37th STOC, pp. 573–581. ACM Press, 2005. [doi:10.1145/1060590.1060675]

[2]   Noga Alon, Oded Goldreich, and Yishay Mansour: Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107–110, 2003. [doi:10.1016/S0020-0190(03)00359-4]

[3]    Sanjeev Arora, Boaz Barak, and David Steurer: Subexponential algorithms for Unique Games and related problems. J. ACM, 62(5):42:1–42:25, 2015. Preliminary version in FOCS’10. [doi:10.1145/2775105]

[4]   Sanjeev Arora, Satish Rao, and Umesh Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1–5:37, 2009. Preliminary version in STOC’04. [doi:10.1145/1502793.1502794]

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

[6]   Mihir Bellare, Oded Goldreich, and Madhu Sudan: Free bits, PCPs, and non-approximability – towards tight results. SIAM J. Comput., 27(3):804–915, 1998. Preliminary version in FOCS’95 and ECCC. [doi:10.1137/S0097539796302531]

[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]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Near-optimal algorithms for Unique Games. In Proc. 38th STOC, pp. 205–214. ACM Press, 2006. [doi:10.1145/1132516.1132547]

[9]   Miroslav Chlebík and Janka Chlebíková: Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover. Discrete Applied Math., 155(2):172–179, 2007. Preliminary version in MFCS’04. [doi:10.1016/j.dam.2006.04.039]

[10]   Irit Dinur and Samuel Safra: The importance of being biased. In Proc. 34th STOC, pp. 33–42. ACM Press, 2002. [doi:10.1145/509907.509915]

[11]   Uriel Feige and Daniel Reichman: On systems of linear equations with two variables per equation. In Proc. 7th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’04), volume 3122 of LNCS, pp. 117–127. Springer, 2004. [doi:10.1007/978-3-540-27821-4_11]

[12]   Ehud Friedgut: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998. [doi:10.1007/PL00009809]

[13]    Michel X. Goemans and David P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. Preliminary version in STOC’94. [doi:10.1145/227683.227684]

[14]   Anupam Gupta, Kunal Talwar, and David Witmer: Sparsest Cut on bounded treewidth graphs: algorithms and hardness results. In Proc. 45th STOC, pp. 281–290. ACM Press, 2013. [doi:10.1145/2488608.2488644, arXiv:1305.1347]

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

[16]   Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright: Improved NP-inapproximability for 2-variable linear equations. pp. 341–360. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.341]

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

[18]   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. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447372]

[19]   Dana Moshkovitz and Ran Raz: Two-query PCP with subconstant error. J. ACM, 57(5):29, 2010. Prleiminary version in FOCS’08. [doi:10.1145/1754399.1754402]

[20]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. Annals of Mathematics, 171(1):295–341, 2010. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]

[21]   Ryan O’Donnell and John Wright: A new point of NP-hardness for Unique-Games. In Proc. 44th STOC, pp. 289–306. ACM Press, 2012. [doi:10.1145/2213977.2214005]

[22]   Anup Rao: Parallel repetition in projection games and a concentration bound. SIAM J. Comput., 40(6):1871–1891, 2011. Preliminary version in STOC’08. [doi:10.1137/080734042]

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

[24]   Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson: Gadgets, approximation, and linear programming. SIAM J. Comput., 29(6):2074–2097, 2000. Preliminary version in FOCS’96. [doi:10.1137/S0097539797328847]

[25]   Ryan Williams: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci., 348(2-3):357–365, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.09.023]