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]