Property Testing

Contact: Mahdi Cheraghchi
Room: BC 148
Tel: 021 6931316
Email: mahdi [dot] cheraghchi [at] epfl [dot] ch

Let P be a property over a family of discrete objects which is true for some of the objects and false for the others. For example, the family can be the set of all undirected graphs over a fixed set of vertices, and the property can be the existence of a triangle, i.e., a subset of three mutually-connected vertices. The property testing problem is the following: Given a member of the family, decide whether it satisfies the property P or is far from satisfying P.

In general the complexity of the problem highly depends on the particular property in question, and so many problems can be regarded as an instance of the property testing problem. However, in almost all interesting situations, one aims to develop a reliable procedure for testing a particular property that is as efficient as possible and only looks at a small fraction of the bit-representation of the given object. Because of the fact that reading the input is costly and the tester can only read a small portion of the input, property testers are almost always randomized, as otherwise an adversary can produce an input object that hides the property in the portion of the input that is never examined by the tester. Also the tester is often allowed to err with some small probability over the choice of its internal coin flips because of the same reason. Therefore, a more precise and common formulation defines a property tester as a randomized procedure that:

• Accepts all the objects that satisfy P with probability one (perfect completeness) or very close to one.
• Rejects all the objects that are far from satisfying P, with high probability (soundness).
• Does not read more than q bits of the input, for some small (ideally constant) q.
• Runs in time polynomial (ideally sublinear) in the length of the input.

The goal of this project, which is a purely theoretical project, is to study several settings of the property testing problem. It will include testing combinatorial properties (e.g., properties in graphs) as well as certain algebraic properties (e.g., testing whether a functionn computes a low-degree polynomial). A fair amount of mathematical maturity and basic knowledge of elementary notions in algebra (e.g., polynomials, finite fields, etc) and probability is required for the project. Understanding of the basic notions can also be acquired during the course of the project.