Algorithmic Aspects of Property Testing in the Dense Graphs Model

Webpage for a paper by Oded Goldreich and Dana Ron


In this paper we consider two refined questions regarding the query complexity of testing graph properties in the adjacency matrix model. The first question refers to the relation between adaptive and non-adaptive testers, whereas the second question refers to testability within complexity that is inversely proportional to the proximity parameter, denoted $\e$. The study of these questions reveals the importance of algorithmic design (also) in this model. The highlights of our study are: We mention that the properties used in the foregoing conflicting results have a similar flavor, although they are of course different.

Material available on-line

Summary and Discussion

For a fixed graph property $\Pi$, we denote by $q=q_\Pi$ the (adaptive/general) query complexity of testing $\Pi$, and by $Q=Q_\Pi$ the corresponding non-adaptive query complexity. All results are demonstrated with quite natural properties, and the upper bounds hold with one-sided error. Issues to be highlighted:
  1. Algorithmic aspects: In Thm 1--3 it is adaptivity (vs non-adaptivity), whereas in Thm 4 it is a non-trivial sampling (vs canonical testers).
  2. Possible gaps between adaptivity and non-adaptivity: Are the possible relations only those stated in the Conj?
  3. Suggested study of query complexity that is linear in $1/\eps$, both in the adaptive and non-adaptive sense (while possibly restricting to one-sided error). This seems the lowest reasonable testing complexity class, and studying it seems a first step towards the study of the $poly(1/\eps)$ query complexity class.

Back to either Oded Goldreich's homepage. or general list of papers.