Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-103 | 12th June 2017 09:18

#### Parameterized Property Testing of Functions

TR17-103
Authors: Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Publication: 12th June 2017 16:43
Specifically, we focus on testing properties of functions. By parameterizing the query complexity in terms of the size $r$ of the image of the input function, we obtain testers for monotonicity and convexity of functions of the form $f:[n]\to \mathbb{R}$ with query complexity $O(\log r),$ with no dependence on $n$. The result for monotonicity circumvents the $\Omega(\log n)$ lower bound by Fischer (Inf. Comput., 2004) for this problem. We present several other parameterized testers, providing compelling evidence that expressing the query complexity of property testers in terms of the input size is not always the best choice.