Self-testing/correcting with applications to numerical problems. (English) Zbl 0795.68131

Summary: Suppose someone gives us an extremely fast program \(P\) that we can call as a black box to compute a function \(f\). Should we trust that \(P\) works correctly? A self-testing/correcting pair for \(f\) allows us to: (1) estimate the probability that \(P(x)\neq f(x)\) when \(x\) is randomly chosen; (2) on any input \(x\), compute \(f(x)\) correctly as long as \(P\) is not too faulty on average. Furthermore, both (1) and (2) take time only slightly more than the original running time of \(P\). We present general techniques for constructing simple to program self-testing/correcting pairs for a variety of numerical functions, including integer multiplication, modular multiplication, matrix multiplication, inverting matrices, computing the determinant of a matrix, computing the rank of a matrix, integer division, modular exponentiation, and polynomial multiplication.


68Q60 Specification and verification (program logics, model checking, etc.)
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI


[1] {\scL. Adleman, M. Huang, and K. Kompella}, Efficient checkers for number-theoretic computations, Inform. and Comput., submitted. · Zbl 0840.11053
[2] Aho, A.; Hopcroft, J.; Ullman, J., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA
[3] Babai, L., Trading group theory for randomness, (), 421-429
[4] Babai, L., E-mail and the power of interaction, () · Zbl 0906.68072
[5] Babai, L.; Fortnow, L.; Lund, K., Non-deterministic exponential time has two-prover interactive protocols, () · Zbl 0774.68041
[6] Beaver, D.; Feigenbaum, J., Hiding instance in multioracle queries, () · Zbl 0733.68005
[7] Beigel, R.; Feigenbaum, J., On the complexity of coherent sets, AT & T technical memorandum, (February 19, 1990)
[8] {\scM. Ben-Or, D. Coppersmith, M. Luby, and R. Rubinfeld}, Convolutions on groups, in preparation. · Zbl 1105.68119
[9] Ben-Or, M.; Goldwasser, S.; Kilian, J.; Wigderson, A., Multi-prover interactive proofs: how to remove intractability, (), 113-131
[10] {\scM. Blum}, “Degning Programs to Check Their Work” ICSI Technical Report TR-88-009.
[11] Blum, M.; Raghavan, P., Program correctness: can one test for it?, (), 127-134
[12] Blum, M.; Kannan, S., Designing programs that check their work, () · Zbl 0886.68046
[13] Blum, M.; Luby, M.; Rubinfeld, R., Program result checking against adaptive programs and in cryptographic settings, () · Zbl 0724.68056
[14] Blum, M.; Luby, M.; Rubinfeld, R., Self-testing/correcting with applications to numerical problems, () · Zbl 0795.68131
[15] Blum, M.; Micali, S.; Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudo-random bits, (), SIAM J. comput., 13, 850-864, (1984) · Zbl 0547.68046
[16] Cleve, R.; Luby, M., A note on self-testing/correcting methods for trigonometric functions, ICSI technical report TR-90-032, (1990)
[17] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, () · Zbl 0702.65046
[18] Feigenbaum, J.; Kannan, S.; Nisan, N., Lower bounds on random self-reducibility, ()
[19] Fortnow, L.; Karloff, H.; Lund, K.; Nisan, N., The polynomial hierarchy has interactive proofs, ()
[20] Freivalds, R., Fast probabilistic algorithms, (), 57-69
[21] Gemmell, P.; Lipton, R.; Rubinfeld, R.; Sudan, M.; Wigderson, A., Self-testing/correcting for polynomials and for approximate functions, ()
[22] Goldwasser, S.; Micali, S.; Rackoff, C.; Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, (), SIAM J. comput., 18, No. 1, 186-208, (1989) · Zbl 0677.68062
[23] Kaminski, M., A note on probabilistically verifying integer and polynomial products, J. assoc. comput. Mach., 36, No. 1, 142-149, (1989) · Zbl 0699.68068
[24] Kannan, S., Program result checking with applications, ()
[25] Karp, R.; Luby, M.; Madras, N., Monte-Carlo approximation algorithms for enumeration problems, J. algorithms, 10, No. 3, 429-448, (1989) · Zbl 0678.65001
[26] Lipton, R., New directions in testing, (), 191-202
[27] Nisan, N., Co-SAT has multi-prover interactive proofs, (November 1989), e-mail announcement
[28] Randall, D., Efficient random generation of nonsingular matrices, Random structures and algorithms, Vol. 4, No. 1, 111-118, (Spring 1993)
[29] Rènyi, A., Probability theory, (1970), North-Holland Amsterdam · Zbl 0206.18002
[30] Rosser, J.B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Illinois J. math., 6, 64-94, (1962) · Zbl 0122.05001
[31] {\scR. Rubinfeld}, “Designing Checkers for Programs that Run in Parallel,” ICSI Technical Report TR-90-040. · Zbl 0843.68042
[32] Rubinfeld, R., Batch checking linear functions, (1990), manuscript
[33] Rubinfeld, R., A mathematical theory of self-checking, self-testing and self-correcting programs, ()
[34] Rubinfeld, R.; Sudan, M., Self-testing polynomial functions efficiently and over rational domains, () · Zbl 0834.68076
[35] {\scA. Schönhage}, personal communication through Michael Fischer.
[36] {\scA. Schönhage and V. Strassen} Schnelle Multiplikation grosser Zahlen, Computing{\bf7}, 281-292.
[37] Shamir, A., Ip = pspace, ()
[38] Strassen, V., Gaussian elimination is not optimal, Numer. math., 13, 354-356, (1969) · Zbl 0185.40101
[39] Yao, A., Coherent functions and program checking, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.