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".

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. All existential results are proved using natural graph properties.

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.

See also text for the official report.

Back to Oded Goldreich's homepage or to the full list of papers.