Name
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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-45878-6_2 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
crucial role,approximation result,main technique,computer vision,machine learning,algebraic function,probabilistically checkable proof,algorithmic issue,self-testing problem,last decade,approximate testing,hardness of approximation,software reliability | Computer science,Hardness of approximation,Oracle,Theoretical computer science,Algebraic function,Mathematical proof,Discrete Fourier transform,Software quality,Distributed computing | Journal |
Volume | Issue | ISSN |
8 | 14 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-43328-7 | 10 | 0.64 |
References | Authors | |
39 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcos A. Kiwi | 1 | 169 | 24.15 |
| Frédéric Magniez | 2 | 570 | 44.33 |
| Miklos Santha | 3 | 728 | 92.42 |