Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey
| |
|
2. Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey
Marcos Kiwi7  , Frédéric Magniez8 and Miklos Santha8
| (7) |
Dept. Ing. Matemática, U. Chile & Ctr. Modelamiento Matemático, UMR 2071, UChile-CNRS, Santiago, 170-3, Chile |
| (8) |
CNRS-LRI, UMR 8623 Université Paris-Sud, 91405 Orsay, France |
Abstract
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.
Gratefully acknowledges the support of Conicyt via Fondecyt No. 1981182 and Fondap in Applied Mathematics, 2000.
Partially supported by the EC thematic network RAND-APX IST-1999-14036. The participation at the Summer School was founded
by the LRI (Orsay) and the IPM (Tehran).
Partially supported by the EC thematic network RAND-APX IST-1999-14036. The participation at the Summer School was founded
by the EGIDE (Paris) and the IPM (Tehran).
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|