Approximate testing with error relative to input size

摘要

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.