Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Manuel Blum and Hal Wasserman. Program result-checking: A theory of testing meets a test of theory. In 35th Annual Symposium on Foundations of Computer Science, pages 382-392, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

Categories and Subject Descriptors: D.2.5 [Software Engineering]: Testing and Debugging; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems -- Computation of transforms; F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs

General Terms: Reliability, Algorithms, Verification

Additional Key Words and Phrases: Built-in testing, concurrent error detection, debugging, fault tolerance, Fourier Transform, result-checking, self-correcting

Selected references

• S. Ar, M. Blum, B. Codenotti, and P. Gemmell. Checking approximate computations over the reals. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 786-795, San Diego, California, 16-18 May 1993.

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991.

• László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 21-31, New Orleans, Louisiana, 6-8 May 1991.

• Donald Beaver and Joan Feigenbaum. Hiding instances in multioracle queries. In 7th Annual Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 37-48, Rouen, France, 22-24 February 1990. Springer.

• Richard Beigel and Joan Feigenbaum. On being incoherent without being very hard. Computational Complexity, 2(1):1-17, 1992.

• Manuel Blum, Will Evans, Peter Gemmell, Sampath Kannan, and Moni Naor. Checking the correctness of memories. Algorithmica, 12(2/3):225-244, August/September 1994.

• Manuel Blum and Sampath Kannan. Designing programs that check their work. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 86-97, Seattle, Washington, 15-17 May 1989.

• Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47(3):549-595, December 1993.

• Ricky W. Butler and George B. Finelli. The infeasibility of quantifying the reliability of life-critical real-time software. IEEE Transactions on Software Engineering, 19(1):3-12, January 1993.

• Funda Ergün. Testing multivariate linear functions: Overcoming the generator bottleneck. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 407-416, Las Vegas, Nevada, 29 May-1 June 1995.

• Lance Fortnow and Michael Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters, 28(5):249-251, 12 August 1988.

• R\=usi\c{n}\v{s} Freivalds. Fast probabilistic algorithms. In J. Be\v{c}vá\v{r}, editor, Mathematical Foundations of Computer Science 1979, volume 74 of Lecture Notes in Computer Science, pages 57-69, Olomouc, Czechoslovakia, 3-7 September 1979. Springer-Verlag.

• Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 32-42, New Orleans, Louisiana, 6-8 May 1991.

• Peter Gemmell and Madhu Sudan. Highly resilient correctors for polynomials. Information Processing Letters, 43(4):169-174, 28 September 1992.

• Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In 27th Annual Symposium on Foundations of Computer Science, pages 174-187, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.

• Richard J. Lipton. Efficient checking of computations. In 7th Annual Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 207-215, Rouen, France, 22-24 February 1990. Springer.

• Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, October 1992.

• Ronitt Rubinfeld. Batch checking with applications to linear functions. Information Processing Letters, 42(2):77-80, 11 May 1992.

• Ronitt Rubinfeld. On the robustness of functional equations. In 35th Annual Symposium on Foundations of Computer Science, pages 288-299, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• Ronitt Rubinfeld and Madhu Sudan. Self-testing polynomial functions efficiently and over rational domains. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 23-32, Orlando, Florida, 27-29 January 1992.

• Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, April 1996.

• J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701-717, October 1980.

• Adi Shamir. IP = PSPACE. In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 11-15, St. Louis, Missouri, 22-24 October 1990. IEEE.

• L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, April 1979.

• Mark N. Wegman and J. Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265-279, June 1981.

• Andrew Chi-Chih Yao. Coherent functions and program checkers (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 84-94, Baltimore, Maryland, 14-16 May 1990.

Shortcuts: