Name
Abstract | ||
|---|---|---|
We formalize the notion and initiate the investigation of approximate testing for arbitrary forms of the error term. Until now only the case of absolute error had been addressed ignoring the fact that often only the most significant figures of a numerical calculation are valid. This work considers approximation errors whose magnitude grows with the size of the input to the program. We demonstrate the viability of this new concept by addressing the basic and benchmark problem of self-testing for the class of linear and polynomial functions. We obtain stronger versions of results of Ergün et al. (Proceedings of the 37th FOCS, 1996, pp. 592-601) by exploiting elegant techniques from Hyers-Ulam stability theory. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0022-0000(03)00004-7 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
arbitrary form,input size,program verification,robustness and stability of functional equations.,absolute error,hyers-ulam stability theory,self-testing programs,elegant technique,numerical calculation,new concept,error term,approximate testing,approximation error,benchmark problem,robustness and stability of functional equations,functional equation | Significant figures,Discrete mathematics,Magnitude (mathematics),Combinatorics,Polynomial,Algorithm,Mathematics,Approximation error,Stability theory | Journal |
Volume | Issue | ISSN |
66 | 2 | Journal of Computer and System Sciences |
Citations | PageRank | References |
1 | 0.36 | 12 |
Authors | ||
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 |