Ramesh Krishnan Pallavoor
Parameterized Property Testing of Functions
Abstract: We investigate the parameters in terms of which the
complexity of sublinear-time algorithms should be expressed. Our goal
is to find input parameters that are tailored to the combinatorics of
the specific problem being studied and design algorithms that run
faster when these parameters are small. This direction enables us to
surpass the (worst-case) lower bounds, expressed in terms of the input
size, for several problems.
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] -> 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.
Joint work with Sofya Raskhodnikova and Nithin Varma (TOCT, 2018).