An Adaptivity Hierarchy Theorem for Property Testing
  Adaptivity is known to play a crucial role in property testing. In
particular, there exist properties for which there is an exponential gap
between the power of \emph{adaptive} testing algorithms, wherein each query may
be determined by the answers received to prior queries, and their
\emph{non-adaptive} counterparts, in which all queries are independent of
answers obtained from previous queries.
  In this work, we investigate the role of adaptivity in property testing at a
finer level. We first quantify the degree of adaptivity of a testing algorithm
by considering the number of "rounds of adaptivity" it uses. More accurately,
we say that a tester is $k$-(round) adaptive if it makes queries in $k+1$
rounds, where the queries in the $i$'th round may depend on the answers
obtained in the previous $i-1$ rounds. Then, we ask the following question:
  Does the power of testing algorithms smoothly grow with the number of rounds
of adaptivity?
  We provide a positive answer to the foregoing question by proving an
adaptivity hierarchy theorem for property testing. Specifically, our main
result shows that for every $n\in \mathbb{N}$ and $0 \le k \le n^{0.99}$ there
exists a property $\mathcal{P}_{n,k}$ of functions for which (1) there exists a
$k$-adaptive tester for $\mathcal{P}_{n,k}$ with query complexity
$\tilde{O}(k)$, yet (2) any $(k-1)$-adaptive tester for $\mathcal{P}_{n,k}$
must make $\Omega(n)$ queries. In addition, we show that such a qualitative
adaptivity hierarchy can be witnessed for testing natural properties of graphs.
