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 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:
-
A gap between the complexity of adaptive and non-adaptive 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})$ non-adaptive queries.
-
In contrast, there exist natural graph properties that
can be tested using $\tildeO(\e^{-1})$ non-adaptive 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 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.
- 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 one-sided error.
Issues to be highlighted:
- 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).
- Possible gaps between adaptivity and non-adaptivity:
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 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.