ECCC-Report TR01-014https://eccc.weizmann.ac.il/report/2001/014Comments and Revisions published for TR01-014en-usTue, 13 Feb 2001 18:56:54 +0200
Paper TR01-014
| Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey |
Marcos Kiwi,
Frederic Magniez,
Miklos Santha
https://eccc.weizmann.ac.il/report/2001/014In 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.
Tue, 13 Feb 2001 18:56:54 +0200https://eccc.weizmann.ac.il/report/2001/014