[Theory Seminar] Sofya Raskhodnikova

October 7, 2015 @ 12:00 pm – 1:00 pm
Title: Fast Algorithms for Testing Geometric Properties
Speaker: Sofya Raskhodnikova


How quickly can we determine if an object satisfies some basic geometric property? For example, is the object a half-plane? Is it convex? Is it connected? If we need to answer such a question exactly, it requires at least as much time as it takes to read the object. In this talk, we will focus on approximate versions of these questions and will discuss how to solve them in time that depends only on the approximation parameter, but not the size of the input.

Specifically, an algorithm is given access to a discretized image represented by an n x n matrix of 0/1 pixel values. Another input to the algorithm is an approximation parameter, epsilon. The algorithm is required to accept images with the desired property and reject (with high probability) images that are far from having the desired property. An image is far if at least an epsilon fraction of its pixels has to be changed to get an image with the required property. For example, in this model, if the algorithm is allowed to read pixels of its choice, the half-plane property and convexity can be tested in time O(1/epsilon). If the algorithm receives access to pixels chosen uniformly and independently at random, then the half-plane property still takes O(1/epsilon) time, but for convexity the (optimal) bound on the running time is O(1/epsilon^(4/3)).

Based on joint work with Piotr Berman and Meiram Murzabulatov.


Sofya Raskhodnikova is an associate professor of Computer Science and Engineering at Penn State. Her research interests include sublinear-time algorithms (in particular, property testing), private data analysis, approximation algorithms, and randomized algorithms. She got her PhD from MIT in 2003. From the fall of 2003 to 2006, she worked at the Hebrew University of Jerusalem, the Weizmann Institute of Science and the Institute for Pure and Applied Mathematics. In 2013–2014, she was on sabbatical leave at Boston University for a special Privacy Year and also participated in thePrivacy Tools project at Harvard University in Spring 2014.