## Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

#### Webpage for a paper by Oded Goldreich and Avi Wigderson

#### Abstract

We study the relation between the query complexity
of adaptive and non-adaptive testers in the dense graph model.
It has been known for a couple of decades that
the query complexity of non-adaptive testers is at most quadratic
in the query complexity of adaptive testers.
We show that this general result is essentially tight;
that is, there exist graph properties for which any
non-adaptive tester must have query complexity that
is almost quadratic in the query complexity of
the best general (i.e., adaptive) tester.

More generally, for every $q:\N\to\N$ such that $q(n)\leq{\sqrt n}$
and constant $c\in[1,2]$,
we show a graph property that is testable in $\Theta(q(n))$ queries,
but its non-adaptive query complexity is $\Theta(q(n)^c)$,
omitting $\poly(\log n)$ factors
and ignoring the effect of the proximity parameter $\epsilon$.
Furthermore, the upper bounds hold for one-sided error testers,
and are at most quadratic in $1/\epsilon$.

These results are obtained through the use of general reductions
that transport properties of ordered structured (like bit strings)
to those of unordered structures (like unlabeled graphs).
The main features of these reductions are query-efficiency
and preservation of distance to the properties.
This method was initiated in
our prior work ({\em ECCC}, TR20-149),
and we significantly extend it here.

#### Material available on-line

**Additioanl grant acknowledgement**:
This project has received funding from the European Research Council (ERC)
under the European Union's Horizon 2020 research and innovation programme
(grant agreement No. 819702).

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