Testing Piecewise Functions
This addresses a theoretical problem in property testing for researchers in computational learning theory, with incremental contributions to understanding query complexities.
The paper tackles the query complexity of property testing for general piecewise functions on the real line in active and passive settings, finding that in active testing, query complexity is independent of the number of pieces, and identifying optimal dependence on pieces for passive testing of piecewise constant functions.
This work explores the query complexity of property testing for general piecewise functions on the real line, in the active and passive property testing settings. The results are proven under an abstract zero-measure crossings condition, which has as special cases piecewise constant functions and piecewise polynomial functions. We find that, in the active testing setting, the query complexity of testing general piecewise functions is independent of the number of pieces. We also identify the optimal dependence on the number of pieces in the query complexity of passive testing in the special case of piecewise constant functions.