Self-Testing/Correcting with Applications to Numerical Problems

Self-Testing/Correcting with Applications to Numerical Problems

1990 | Manuel Blum, Michael Luby, Ronitt Rubinfeld
This paper introduces self-testing/correcting pairs for numerical problems, allowing programs to verify their correctness and correct errors. A self-testing/correcting pair consists of two programs: a self-tester that estimates the probability of errors in a program and a self-corrector that computes the correct output even if the program is faulty. These pairs are efficient, with running times only slightly more than the original program. The paper presents general techniques for constructing self-testing/correcting pairs for various numerical problems, including integer multiplication, modular multiplication, matrix multiplication, matrix inversion, determinant computation, matrix rank, integer division, modular exponentiation, and polynomial multiplication. The self-tester estimates the error probability of a program, while the self-corrector computes the correct output for any input, assuming the error probability is sufficiently low. The self-testing/correcting approach is more efficient and reliable than traditional verification and testing methods. It allows for the use of a single pair of programs to test and correct any program that computes a given function, regardless of the program's correctness. This makes it particularly useful for programs that are fast but potentially faulty. The paper also discusses the theoretical foundations of self-testing/correcting, including the use of random self-reducibility and linearity properties. These properties enable the construction of self-testers and self-correctors that can handle a wide range of numerical problems. The self-tester for the mod function, for example, uses linear and neighbor consistency tests to estimate the error probability of a program. The paper concludes with a discussion of future work, including the potential for self-testing/correcting pairs for other important functions and the development of more efficient self-correctors for important numerical problems. The results demonstrate the effectiveness of self-testing/correcting pairs in ensuring the correctness of programs that compute numerical functions.This paper introduces self-testing/correcting pairs for numerical problems, allowing programs to verify their correctness and correct errors. A self-testing/correcting pair consists of two programs: a self-tester that estimates the probability of errors in a program and a self-corrector that computes the correct output even if the program is faulty. These pairs are efficient, with running times only slightly more than the original program. The paper presents general techniques for constructing self-testing/correcting pairs for various numerical problems, including integer multiplication, modular multiplication, matrix multiplication, matrix inversion, determinant computation, matrix rank, integer division, modular exponentiation, and polynomial multiplication. The self-tester estimates the error probability of a program, while the self-corrector computes the correct output for any input, assuming the error probability is sufficiently low. The self-testing/correcting approach is more efficient and reliable than traditional verification and testing methods. It allows for the use of a single pair of programs to test and correct any program that computes a given function, regardless of the program's correctness. This makes it particularly useful for programs that are fast but potentially faulty. The paper also discusses the theoretical foundations of self-testing/correcting, including the use of random self-reducibility and linearity properties. These properties enable the construction of self-testers and self-correctors that can handle a wide range of numerical problems. The self-tester for the mod function, for example, uses linear and neighbor consistency tests to estimate the error probability of a program. The paper concludes with a discussion of future work, including the potential for self-testing/correcting pairs for other important functions and the development of more efficient self-correctors for important numerical problems. The results demonstrate the effectiveness of self-testing/correcting pairs in ensuring the correctness of programs that compute numerical functions.
Reach us at info@study.space
Understanding Self-testing%2Fcorrecting with applications to numerical problems