Self-testing/correcting with applications to numerical problems

Abstract

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 (