Self-Testing/Correcting with Applications to Numerical Problems (Revised Version)

TitleSelf-Testing/Correcting with Applications to Numerical Problems (Revised Version)
Publication TypeTechnical Report
Year of Publication1991
AuthorsBlum, M. E., Luby M., & Rubinfeld R.
Other Numbers692

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 {em self-testing/correcting pair} for $f$ allows us to: (1) estimate the probability that $P(x)ot= f(x)$ when $x$ is randomly chosen; (2) on {em 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.

Bibliographic Notes

ICSI Technical Report TR-91-062

Abbreviated Authors

M. Blum, M. Luby, and R. Rubinfeld

ICSI Publication Type

Technical Report