Algorithmic Aspects of Property Testing in the Dense Graphs Model
Webpage for a paper by Oded Goldreich and Dana Ron
Abstract
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 nonadaptive 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:

A gap between the complexity of adaptive and nonadaptive testers.
Specifically, there exists a (natural) graph property that
can be tested using $\tildeO(\e^{1})$ adaptive queries,
but cannot be tested using $o(\e^{3/2})$ nonadaptive queries.

In contrast, there exist natural graph properties that
can be tested using $\tildeO(\e^{1})$ nonadaptive queries,
whereas $\Omega(\e^{1})$ queries are required even in the
adaptive case.
We mention that the properties used in the
foregoing conflicting results have a similar flavor,
although they are of course different.
Material available online
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 nonadaptive query complexity.
 Thm [AFKS, GT]: For every $\Pi$, it holds that $Q=O(q^2)$.
 Thm 1: There exists $\Pi$ such that $Q=tildeTheta(q^{4/3})$.
 Thm 2: There exists $\Pi$ such that $Q=tildeOmega(q^{3/2})$.
 Conj: For every $t>1$, there exists $\Pi$
such that $Q=tildeTheta(q^{2(2/t)})$.
 Thm 3: Conj holds for promise problems.
 Thm 4: There exists infinitely many $\Pi$
such that $Q=tildeTheta(q})=tildeTheta(1/\eps)$.
All results are demonstrated with quite natural properties,
and the upper bounds hold with onesided error.
Issues to be highlighted:
 Algorithmic aspects: In Thm 13 it is adaptivity
(vs nonadaptivity), whereas in Thm 4 it is a nontrivial
sampling (vs canonical testers).
 Possible gaps between adaptivity and nonadaptivity:
Are the possible relations only those stated in the Conj?
 Suggested study of query complexity that is linear in $1/\eps$,
both in the adaptive and nonadaptive sense
(while possibly restricting to onesided 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.