Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-039 | 7th April 2008 00:00

Algorithmic Aspects of Property Testing in the Dense Graphs Model


Authors: Oded Goldreich, Dana Ron
Publication: 7th April 2008 22:50
Downloads: 1219


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.

ISSN 1433-8092 | Imprint