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]