Noisy Interpolating Sets for Low-Degree Polynomials

by Zeev Dvir and Amir Shpilka

Theory of Computing, Volume 7(1), pp. 1-18, 2011

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. [doi:10.1145/278298.278306]

[2]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. [doi:10.1145/273865.273901]

[3]    László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complexity, 3(4):307–318, 1993. [doi:10.1007/BF01275486]

[4]   Eli Ben-Sasson and Madhu Sudan: Limits on the rate of locally testable affine-invariant codes. Electron. Colloq. on Comput. Complexity (ECCC), 17:108, 2010. [ECCC:TR10-108]

[5]   Andrej Bogdanov: Pseudorandom generators for low degree polynomials. In Proc. 37th STOC, pp. 21–30. ACM Press, 2005. [doi:10.1145/1060590.1060594]

[6]   Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464–2486, 2010. [doi:10.1137/070712109]

[7]   Russell Impagliazzo and Avi Wigderson: P=BPP unless E has subexponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pp. 220–229. ACM Press, 1997. [doi:10.1145/258533.258590]

[8]   J. Justesen: A class of constructive asymptotically good algebraic codes. IEEE Trans. Inform. Theory, 18(5):652–656, 1972. [doi:10.1109/TIT.1972.1054893]

[9]   Shachar Lovett: Unconditional pseudorandom generators for low degree polynomials. Theory of Computing, 5(1):69–82, 2009. [doi:10.4086/toc.2009.v005a003]

[10]   F. J. MacWilliams and N. J. A. Sloane: The Theory of Error-Correcting Codes, Part II. North-Holland, 1977.

[11]   Ronen Shaltiel and Christopher Umans: Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172–216, 2005. [doi:10.1145/1059513.1059516]

[12]   Madhu Sudan, Luca Trevisan, and Salil Vadhan: Pseudorandom generators without the XOR lemma. J. Comput. System Sci., 62(2):236–266, 2001. [doi:10.1006/jcss.2000.1730]

[13]   Amnon Ta-Shma, David Zuckerman, and Shmuel Safra: Extractors from Reed-Muller codes. J. Comput. System Sci., 72(5):786–812, 2006. [doi:10.1016/j.jcss.2005.05.010]

[14]   Emanuele Viola: The sum of d small-bias generators fools polynomials of degree d. Comput. Complexity, 18(2):209–217, 2009. [doi:10.1007/s00037-009-0273-5]