Self-testing/correcting with applications to numerical problems
Manuel Blum, Michael G. Luby, Ronitt Rubinfeld · 1990
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 allows us to: (1) estimate the probability that P(x) 5~ 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 problems, 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.