Property Testing is the study of the following family of tasks: Given access to a (very large) object (e.g. function), we are interested in determining (w.h.p.) whether the object has a certain predetermined property (e.g. linearity) or is far from having the property. In "far'' we mean that a non-negligible part of the object should be modified so that it have the property. One natural view of property testing is that it is a relaxation of exactly deciding whether the object has the property or not. An alternative view is that property testing is a relaxation of learning the object.

In this talk I will focus on the problem of testing of clustering. Namely, here the "object'' is a large set of points X, and the property is "being-clusterable". That is, we would like to determine whether X can be partitioned into at most k subsets (clusters) such that the cost associated with the partition is at most b. We study several cost measures and several underlying metrics, and give algorithms that use a sample from X that has size independent of |X|.

This is joint work with Noga Alon, Seannie Dar and Michal Parnas.