Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Adaptive vs Nonadaptive queries:
TR13-067 | 2nd May 2013
Oded Goldreich

On Multiple Input Problems in Property Testing

Revisions: 1

We consider three types of multiple input problems in the context of property testing.
Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:
Given a sequence of $m$ inputs, output a sequence ... more >>>

TR20-160 | 2nd November 2020
Oded Goldreich, Avi Wigderson

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

Revisions: 2

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 ... more >>>

ISSN 1433-8092 | Imprint