Let's Try and Be More Tolerant: On Tolerant Property Testing and Distance Approximation

A property testing algorithm is required to accept objects that have a prespecified property P and reject those that are relatively far from having P. To this end, it is given query (or sampling) access to the object, and is allowed a small failure probability. Its query/sample complexity is required to be sublinear in the size of the object.

A tolerant testing algorithm is required to also accept objects that are relatively close to having the property (while still rejecting those that are far), and a distance-approximation algorithm is required to approximate the distance to having a property. Such algorithms were first explicitly defined in the work of Parnas, Rubinfeld, and Ron (JCSS 2006).

In this talk, Dana Ron will present several tolerant testing/distance-approximation algorithms for a variety of object-types and properties, and discuss some hardness results. Examples include the properties of bipartiteness of graphs, monotonicity of functions, uniformity of distributions, and subsequence-freeness.

Speaker: Dana Ron, Tel Aviv University

Register at weblink to attend in person.  Lecture will be available on YouTube later (see weblink)