Satisfying Degree-$d$ Equations over $GF[2]^n$
by Johan Håstad
Theory of Computing, Volume 9(27), pp. 845-862, 2013
Bibliography with links to cited articles
[1] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Preliminary version in FOCS’92. See also at ECCC. [doi:10.1145/278298.278306]
[2] Per Austrin and Johan Håstad: On the usefulness of predicates. ACM Trans. Computation Theory, 5(1):1:1–1:24, 2013. Preliminary version in CCC’12. [doi:10.1145/2462896.2462897]
[3] Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. Preliminary version in CCC’08. See also at ECCC. [doi:10.1007/s00037-009-0272-6]
[4] Mihir Bellare, Oded Goldreich, and Madhu Sudan: Free bits, PCPs, and nonapproximability—towards tight results. SIAM J. Comput., 27(3):804–915, 1998. Preliminary version in FOCS’95. See also at ECCC. [doi:10.1137/S0097539796302531]
[5] Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]
[6] Johan Håstad: Satisfying degree-d equations over GF[2]n. In Proc. 14th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’11), pp. 242–253. Springer, 2011. [doi:10.1007/978-3-642-22935-0_21]
[7] Johan Håstad, Steven Phillips, and Shmuel Safra: A well-characterized approximation problem. Information Processing Letters, 47(6):301–305, 1993. Preliminary version in ISTCS’93. [doi:10.1016/0020-0190(93)90076-L]
[8] Tadao Kasami and Nobuki Tokura: On the weight structure of Reed-Muller codes. IEEE Trans. Inform. Theory, 16(6):752–759, 1970. [doi:10.1109/TIT.1970.1054545]
[9] Dana Moshkovitz and Ran Raz: Two-query PCP with subconstant error. J. ACM, 57(5):29:1–29:29, 2010. Preliminary version in FOCS’08. See also at ECCC. [doi:10.1145/1754399.1754402]
[10] Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary version in STOC’95. [doi:10.1137/S0097539795280895]
[11] Emanuele Viola: The sum of D small-bias generators fools polynomials of degree D. Comput. Complexity, 18(2):209–217, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0273-5]