演讲人： Dana Ron Tel Aviv University, Israel
时间： 2006-04-14 15:00-2006-04-14 16:00
地点：FIT Building,Tsinghua University
内容：
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.
个人简介:
