Complexity Theoretic Aspects of Property Testing

Oded Goldreich

Notes for the MFO meeting on Complexity Theory. In the meeting I only managed to talk of the first work.

For the purpose of this meeting, I would say that "Property Testing is a PCP of Proximity without the proof part".

Normally, I'd say that property Testing is concerned with approximate decisions, where the task is distinguishing between objects having a predetermined property and objects that are ``far'' from having this property. Specifically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We consider (randomized) algorithms that may query the function at arguments of their choice, and seek algorithms of very low complexity (i.e., much lower than the size of the function's domain).

Relation between adaptive and non-adaptive query complexity of graph properties in the adjacency matrix model

For any fixed property $Pi$, let $q$ denote the query complexity of (general, i.e., adaptive) testing of $Pi$, and $Q$ dente the corresponding non-adaptive query complexity (i.e., which refers to non-adaptove testers of $Pi$). Following is a list of known and conjectured results, where $tildeOmega$ and $tildeTheta$ denote bounds with a slackness of a polylogarithmic factor.

THM: For any graph property in the adjacency matrix model, it holds that $Q=O(q^2)$. (See GT)
THM [GR]: There exist graph properties in the adjacency matrix model such that $Q=tildeTheta(q)$.
Actually, $Q=O(q)$ and even $Q=q$ are known too.
THM [GR]: There exists a graph property in the adjacency matrix model such that $Q=tildeTheta(q^{4/3})$.
THM [GR]: There exists a graph property in the adjacency matrix model such that $Q=tildeOmega(q^{3/2})$.
CONJ [GR]: For every integer $t>2$, there exists a graph property in the adjacency matrix model such that $Q=tildeTheta(q^{2-(2/t)})$.
This conjecture is supported by a theorem that establish the same relation relation for a promise problem.

All existential results are proved using natural graph properties.

O. Goldreich and L. Trevisan, Three Theorems regarding Testing Graph Properties, 2001.
O. Goldreich and D. Ron, Algorithmic Aspects of Property Testing in the Dense Graphs Model, April 2008.

Hierarchy Theorems for Property Testing

Such results are proved for three central models of property testing: the general model of generic function, the model of bounded-degree graph properties, and the model of dense graph properties (in the adjacency matrix model). From a technical perspective, the treatment of the latter is most interesting, since it raises and resolves various natural questions regarding graph blow-up. For details, see my paper with M. Krivelevich, I. Newman and E. Rozenberg.