Improved algorithms and new models in property testing
Pallavoor Suresh, Ramesh Krishnan
MetadataShow full item record
We study sublinear-time algorithms for testing fundamental properties of functions and graphs. Sublinear-time algorithms run in time sublinear in the input size and are especially useful for processing massive datasets. We investigate variants of the property testing model, which was introduced by Rubinfeld and Sudan (SIAM J. Comput., 1996) and Goldreich, Goldwasser and Ron (J. ACM, 1998) to formally study sublinear-time algorithms. The focus of this thesis is on designing better property testers, deepening our understanding of their limitations, and proposing new angles for investigating sublinear-time algorithms. First, we study the problem of testing unateness of real-valued functions over high-dimensional domains. A function over a multi-dimensional domain is unate if, along each dimension, the function is either nonincreasing or nondecreasing. We give efficient unateness testers and prove that they are optimal. We then focus on testing monotonicity of functions when the input functions are partially corrupted or partially erased. We prove that, for some settings of parameters, testing monotonicity of functions with corrupted or erased values is exponentially harder than testing monotonicity of functions with neither corruptions nor erasures. We then investigate the parameters in terms of which the complexity of property testers should be expressed. The complexity of algorithms and, in particular, property testers is usually expressed in terms of the size of the input. We prove that certain parameters capture the complexity of testing problems better than the input size, providing compelling evidence that the input size may not always be the best parameter to express the complexity of sublinear-time algorithms. Finally, we turn our attention towards testing properties of graphs. We first provide an algorithm for testing connectedness of graphs and prove that it is optimal. We then define a new model for studying graphs with missing information and investigate the problems of testing connectedness and estimating the average degree of graphs in the new model.
RightsAttribution 4.0 International