Ramesh Pallavoor Suresh - "Improved Algorithms and New Models in Property Testing" - PhD Final Defense
- Starts: 1:00 pm on Tuesday, July 14, 2020
- Ends: 3:00 pm on Tuesday, July 14, 2020
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 along that dimension. 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.
- via Zoom