Let’s Try and Be More Tolerant: On Tolerant Property Testing and Distance Approximation | Richard M. Karp Distinguished Lecture

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, as well as discuss some hardness results. Examples include the properties of bipartiteness of graphs, monotonicity of functions, uniformity of distributions, and subsequence-freeness.

Dana Ron is a professor in the School of Electrical Engineering at Tel Aviv University. She received her PhD from the Hebrew University in 1995. She was an NSF postdoc at MIT, a Bunting scholar at Radcliffe, a member of the Radcliffe cluster on randomness in computation, and a visiting scientist at Columbia University. During her PhD, she worked in the area of computational learning theory, and during her postdoc period was one of the founders of the area of property testing. Her current research focus is on various types of sublinear-time algorithms. She is an EATCS fellow and an ACM fellow.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science and is geared toward a broad scientific audience.

Light refreshments will be available at 4 p.m., prior to the start of the lecture. 

The lecture recording URL will be emailed to registered participants. This URL can be used for immediate access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about 12 to 15 days following each presentation unless otherwise noted.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.