Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR20-160 | 8th September 2021 20:12

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

RSS-Feed




Revision #3
Authors: Oded Goldreich, Avi Wigderson
Accepted on: 8th September 2021 20:12
Downloads: 454
Keywords: 


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.



Changes to previous version:

Adding open problems (Section 7)


Revision #2 to TR20-160 | 26th February 2021 13:35

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





Revision #2
Authors: Oded Goldreich, Avi Wigderson
Accepted on: 26th February 2021 13:35
Downloads: 413
Keywords: 


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.



Changes to previous version:

New Sec 1.4 and 6, featuring an extension
of Thms 1.2-1.4 to complexities that may also (or only) depend on the proximity parameter.


Revision #1 to TR20-160 | 5th November 2020 16:10

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





Revision #1
Authors: Oded Goldreich, Avi Wigderson
Accepted on: 5th November 2020 16:10
Downloads: 459
Keywords: 


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.



Changes to previous version:

Removing a side comment that was not fully justified.


Paper:

TR20-160 | 2nd November 2020 17:23

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





TR20-160
Authors: Oded Goldreich, Avi Wigderson
Publication: 2nd November 2020 17:24
Downloads: 814
Keywords: 


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.



ISSN 1433-8092 | Imprint