Export to Refworks Export to EndNote Email
Report an Issue

Robust Models For Property Testing

Author:
Dixit, Kashyap
Published:
[University Park, Pennsylvania] : Pennsylvania State University, 2015.
Physical Description:
1 electronic document
Additional Creators:
Furer, Martin and Raskhodnikova, Sofya
Access Online

Availability

I Want It

Finding items...

Restrictions on Access:
Open Access.
Summary:
Property testing [Rubinfeld Sudan 96,Goldreich Goldwasser Ron 98] is a formal framework for studying approximate sublinear time randomized algorithms for decision problems. These algorithms have black-box query access to the input functions. Property testers are required to distinguish between functions that satisfy a given property from those that are 'far' from satisfying the property. Informally, a function is far from satisfying a given property if many function values need to be changed to satisfy the property. The notion of distance from a property is central to property testing. The distance of a function f : D → R from a property P is the smallest distancebetween f and any function g : D → R that satisfies P. One of the most widely studied model [Rubinfeld Sudan 96,Goldreich Goldwasser Ron 98] uses the relative Hamming distance as the notion of distance between two functions. That is, the distance between two functions f : D → Rand g : D → R is the fraction of domain points on which f and g differ. A long line of work has been dedicated to the design and study of sublinear time algorithms for a number of function properties using this model.This works focuses on studying practical generalizations of the aforementioned model. In the first part, we work with generalizing the notion of distance between functions. The relative Hamming distance can also be viewed as the distance between functions with respect to the uniformdistribution. As part of our study, we design optimal testers for a large class of functions properties, called the bounded derivative properties, when the distance is measured with respect to a known or an unknown product distribution. The class of bounded derivative properties include well studiedfunction properties like monotonicity and the Lipschitz property.The second part of our work focuses on a generalization of the input access model. In many practical scenarios, a black-box access to the whole input function might not be possible. Some of the function values might not be available to the tester due to privacy requirements or adversarialerasures.We refer to such domain points as erased. The location of an erasure becomes known to the tester only upon querying the respective domain point. We design efficient erasure-resilient sublinear time testers for a large number of properties including the bounded derivative properties and convexity. Some of our testers are almost optimal, even in the case when a constant fraction ofpoints are erased.
Other Subject(s):
Genre(s):
Dissertation Note:
Ph.D. Pennsylvania State University 2015.
Reproduction Note:
Microfilm (positive). 1 reel ; 35 mm. (University Microfilms 10-025227)
Technical Details:
The full text of the dissertation is available as an Adobe Acrobat .pdf file ; Adobe Acrobat Reader required to view the file.
View MARC record | catkey: 16834410