Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-014 | 7th February 2001 00:00

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey



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

ISSN 1433-8092 | Imprint