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]