On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
Theory of Computing, Volume 13(10), pp. 1-19, 2017
Bibliography with links to cited articles
[1] Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications. Combinatorica, 23(3):365–426, 2003. Preliminary version in STOC’97. [doi:10.1007/s00493-003-0025-0]
[2] Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou: Better balance by being biased: A 0.8776-approximation for max bisection. ACM Trans. Algorithms, 13(1):2:1–2:27, 2016. Preliminary version in SODA’13. [doi:10.1145/2907052, arXiv:1205.0458]
[3] Per Austrin and Johan Håstad: Randomly supported independence and resistance. SIAM J. Comput., 40(1):1–27, 2011. Preliminary version in STOC’09. [doi:10.1137/100783534]
[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] Per Austrin, Ryan O’Donnell, Li-Yang Tan, and John Wright: New NP-hardness results for 3-coloring and 2-to-1 label cover. ACM Trans. Comput. Theory, 6(1):2:1–2:20, 2014. Preliminary version in APPROX’12. [doi:10.1145/2537800, arXiv:1210.5648]
[6] 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]
[7] Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman: Optimal testing of Reed-Muller codes. In Proc. 51st FOCS, pp. 488–497. IEEE Comp. Soc. Press, 2010. Another version appears as a chapter in Property Testing, O. Goldreich, ed., LNCS vol. 6390, 2010, pp. 269–275. [doi:10.1109/FOCS.2010.54, arXiv:0910.0641]
[8] Siu On Chan: Approximation resistance from pairwise independent subgroups. J. ACM, 63(3):27:1–27:32, 2016. Preliminary version in STOC’13. [doi:10.1145/2873054]
[9] Irit Dinur and Venkatesan Guruswami: PCPs via low-degree long code and hardness for constrained hypergraph coloring. Israel J. Math., 209(2):611–649, 2015. Preliminary version in FOCS’13. [doi:10.1007/s11856-015-1231-3]
[10] 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]
[11] Venkatesan 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]
[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] Jonas Holmerin and Subhash Khot: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. In Proc. 36th STOC, pp. 11–20. ACM Press, 2004. [doi:10.1145/1007352.1007362]
[14] Subhash Khot: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025–1071, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447037]
[15] 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]
[16] 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]
[17] Erez Petrank: The hardness of approximation: Gap location. Comput. Complexity, 4(2):133–157, 1994. Preliminary version in ISTCS’93. [doi:10.1007/BF01202286]
[18] Harald Räcke: Optimal hierarchical decompositions for congestion minimization in networks. In Proc. 40th STOC, pp. 255–264. ACM Press, 2008. [doi:10.1145/1374376.1374415]
[19] 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]
[20] 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]