Department of Computer Science
University of Rochester
beygel@cs.rochester.edu
Property Testing is concerned with the question of determining whether a given object has some predetermined property of is ``far'' from any object having this property. The properties considered are very natural, e.g. bipartiteness or acyclicity of graphs, monotonicity of functions, clusterability of point sets. One is allowed to ``probe into'' the object (i.e. make a small number of LOCAL checks), and is required to assert with high probability whether the object has some GLOBAL property (or it has to be significantly modified in order to have the property). This relaxation yields an interesting notion of approximation (being close to having a property), and in some cases allows to have extremely fast algorithms, whose running time is significantly smaller than (or even independent of) the size of the object. We survey recent results in the area, most notably due to Goldreich.
Colloquia Series page.