Fifty Shades of Adaptivity (in Property Testing)

Abstract: 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 /adaptive/ testing algorithms, wherein each query
may be determined by the answers received to prior queries, and their
/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 integer n and 0 <= k <= n^{0.33} there
exists a property P_{n,k} of functions for which (1) there exists a
k-adaptive tester for P_{n,k} with query complexity ~O(k), yet (2) any
(k-1)-adaptive tester for P_{n,k} must make ~Omega(n/k^2) queries. In
addition, we show that such a qualitative adaptivity hierarchy can be
witnessed for testing natural properties of graphs.

Joint work with Tom Gur (Weizmann Institute).