TR01-014 Authors: Marcos Kiwi, Frederic Magniez, Miklos Santha

Publication: 13th February 2001 18:56

Downloads: 1841

Keywords:

In the late 80's Blum, Luby, Rubinfeld, Kannan et al. pioneered

the theory of self-testing as an alternative way of dealing with

the problem of software reliability.

Over the last decade this theory played a crucial role in

the construction of probabilistically checkable proofs and

the derivation of hardness of approximation results.

Applications in areas like computer vision, machine learning,

and self-correcting programs were also established.

In the self-testing problem one is interested in determining (maybe

probabilistically) whether a function to which one has

oracle access satisfies a given property.

We consider the problem of testing algebraic functions

and survey over a decade of research in the area.

Special emphasis is given to illustrate the scenario

where the problem takes place and to the main techniques used

in the analysis of tests.

A novel aspect of this work is the separation it advocates

between the mathematical and algorithmic issues that arise in the theory of

self-testing.