Self-testing polynomial functions efficiently and over rational domains

ABSTRACT

In this paper we give the first self-testers and checkers for polynomials over rational and integer domains. We also show significantly stronger bounds on the efficiency of a simple modification of the algorithm for self-testing polynomials over finite fields given in [8].

REFERENCES

• 1: Babai, L., Fortnow, L., Lund, C., "Non-Deterministic Exponential Time has Two-Prover Interactive Protocol~", Proccedinga of the 31st Annual Symposium on Foundations of Computer Science,, 1990.
• 2: Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
• 3: Manuel Blum , Sampath Kannan, Designing programs that check their work, Journal of the ACM (JACM), v.42 n.1, p.269-291, Jan. 1995 [doi>10.1145/200836.200880]
• 4: M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
• 5: M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100225]
• 6: U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
• 7: FreivaJds, R., "Fast Probabilistic Algorithms'', Springer Vefiag Lecture Notes in CS No. 74, Mathematical Foundations of CS, 57-69 (1979).
• 8: Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
• 9: Lipton, R.J., "New directions in Testing," in Distributed Computing and Cryptography, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 2, 1991, pp. 191-202.
• 10: Carsten Lund, The Power of Interaction, University of Chicago, Chicago, IL, 1991
• 11: Shen, Sasha, personal communication, May 1991.
• 12: Van Der Waerden, B.L., Algebra, Vol. 1, Frederick Ungar Publishing Co., Inc., pp. 86-91, 1970.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
      D.2.5 Testing and Debugging

General Terms:
Theory, Verification