Property testing in the presence of erased data

p>Property testing is a formal framework to design algorithms for large datasets. The traditional definition of property testing [Rubinfeld & Sudan 96, Goldreich, Goldwasser & Ron] abstracts datasets as functions and assumes that an algorithm (also called tester) can query points in the domain of a function to obtain the corresponding values. The task of the tester is to distinguish, with probability 2/3, between the case that the function f being queried belongs to a set (property) P and the case that f is `far' from every function in P, for an appropriate measure of distance.

One of the key assumptions in the above definition, that the tester has access to function values at all of the queried domain points, is not applicable to most real-life datasets. It could be the case that some or several of the function values are kept hidden for privacy reasons, or erased by mistake or by an adversary. Querying such erased points does not provide an algorithm with any information about the function. Moreover, it might happen that, an algorithm, by not knowing the locations of these erasures, makes a lot of queries to erased points and turns out entirely useless. In the talk, I will describe the erasure-resilient property testing model that we defined to account for the occurrence of erasures in datasets. We will then present and analyse our erasure-resilient tester for monotonicity of functions.

Joint work with Kashyap Dixit, Sofya Raskhodnikova and Abhradeep Thakurta.

Nithin Varma is a third year PhD student working with Dr. Sofya Raskhodnikova in the Theory and Algorithms Group at the Department of Computer Science and Engineering, Pennsylvania State University. His interest areas include Sublinear algorithms, Streaming algorithms and Graph algorithms.

Before joining Penn State, he was a member of the Theoretical Computer Science Group working with Dr. Kavitha Telikepalli at Tata Institute of Fundamental Research, India, from where he graduated with a Master's degree.