Speaker: Dana Ron Tel Aviv University, Israel
Time: 2006-04-12 15:00-2006-04-12 16:00
Venue: FIT Building,Tsinghua University

Abstract:

Property testing problems are a relaxation of decision problems. Namely, instead of deciding whether an input (e.g., a graph) has a certain property (e.g., is bipartite) or *not*, the goal is to decide whether the input has the property or *is relatively far* from having the property. In "relatively far" we mean that at least an \epsilon-fraction of the input should be modified so that the input obtain the property, where \epsilon is a given parameter. As we relax the task, we seek algorithms that are very efficient. In particular, we seek algorithms that run in time that is sublinear (and possibly even independent of) the input size.
In this series of lectures I plan to give a short introduction to property testing, with a focus on testing graph properties.

Short Bio: