Self-Testing/Correcting with Applications to Numerical Problems

Self-Testing/Correcting with Applications to Numerical Problems

1990 | Manuel Blum, Michael Luby, Ronitt Rubinfeld
The paper introduces the concept of self-testing/correcting pairs for numerical problems, which allow for estimating the probability that a given program $P$ computes a function $f$ incorrectly and, if the error probability is sufficiently low, correctly computing $f$ on any input. The authors present general techniques for constructing simple and efficient self-testing/correcting pairs for various numerical problems, including integer multiplication, modular multiplication, matrix multiplication, matrix inversion, determinant computation, rank computation, integer division, modular exponentiation, and polynomial multiplication. These techniques leverage the property of random self-reducibility, where the output of a function can be expressed as a function of smaller inputs and their outputs. The paper also discusses the use of libraries of programs to aid in testing and correcting, and provides specific examples of self-testing/correcting pairs for matrix operations. The authors conclude with future directions, including the design of self-testing/correcting pairs for other functions and the development of batch self-correctors to reduce overhead.The paper introduces the concept of self-testing/correcting pairs for numerical problems, which allow for estimating the probability that a given program $P$ computes a function $f$ incorrectly and, if the error probability is sufficiently low, correctly computing $f$ on any input. The authors present general techniques for constructing simple and efficient self-testing/correcting pairs for various numerical problems, including integer multiplication, modular multiplication, matrix multiplication, matrix inversion, determinant computation, rank computation, integer division, modular exponentiation, and polynomial multiplication. These techniques leverage the property of random self-reducibility, where the output of a function can be expressed as a function of smaller inputs and their outputs. The paper also discusses the use of libraries of programs to aid in testing and correcting, and provides specific examples of self-testing/correcting pairs for matrix operations. The authors conclude with future directions, including the design of self-testing/correcting pairs for other functions and the development of batch self-correctors to reduce overhead.
Reach us at info@study.space
[slides] Self-testing%2Fcorrecting with applications to numerical problems | StudySpace