Self-Testing/Correcting with Applications to Numerical Problems
| Title | Self-Testing/Correcting with Applications to Numerical Problems |
| Publication Type | Technical Report |
| Year of Publication | 1990 |
| Authors | Blum, M. E., Luby M., & Rubinfeld R. |
| Other Numbers | 605 |
| 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 for f allows us to: (1) estimate the probability that P(x) is not equal to 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 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-041.pdf |
| Bibliographic Notes | ICSI Technical Report TR-90-041 |
| Abbreviated Authors | M. Blum, M. Luby, and R. Rubinfeld |
| ICSI Publication Type | Technical Report |