Property Testing Workshop

Property Testing and Sublinear Time Algorithms
June 17-18, 2013
Dan Carmel Hotel, Haifa
Organizers: Eldar Fischer (CS Technion) and Ilan Newman (CS Haifa University)

When trying to decide a whether an input satisfies a given property, the most common scenario is where most of the input has to be read to obtain enough information for determining the decision problem. Thus follows an almost trivial lower bound of Theta(n) on the time complexity of the deciding algorithm, where n is the input size.

Property testing deals with a notion of approximation that many times has the effect of allowing an answer that does not require a full reading of the input. In its general setting, instead of deciding whether the input satisfies the property, it is deemed sufficient to accept any input that satisfies the property, while rejecting any input that is far from any alternative that satisfies the property. Such a testing algorithm has a "random read" (oracle) access to the input, and needs only to follow the above acceptance and rejection requirements with sufficiently high probability.

Not having to read the entire input sometimes (but not always) also allows for sublinear time algorithms, algorithms whose running time is o(n). At times, instead of a gap decision problem as above, parameter approximation problems are considered, one example being approximating the actual distance of the input from the property, rather than merely distinguishing the two cases outlined above.

Property testing first emerged for algebraic properties (such as a function being linear) in the context of proof and program verification, and about a decade later has entered the realm of combinatorial properties. The last two decades saw rapid growth in the investigation of property testing, including some recent classification results. Additional growth took place in related areas, such as sublinear time algorithms, approximation of properties of distributions through sampling, proofs of proximity, and other topics.

The workshop's scope includes property testing, sublinear time algorithms, and their related topics.

Program is available here



This workshop is primarily funded by the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013), ERC grant agreement number 202405.