An Adaptivity Hierarchy Theorem for Property Testing

Clément L. Canonne, Tom Gur

Introduction

Property testing is a subfield of theoretical computer science focused on designing randomized algorithms that can determine whether a massive input—such as a large graph or a long string—possesses a specific property or is "far" from having it. Crucially, these algorithms must make their decision by inspecting only a tiny, sublinear fraction of the input.

Traditionally, property testing research has categorized algorithms into two distinct classes: non-adaptive and adaptive. Non-adaptive testers decide all their queries in advance, while adaptive testers can use the results of previous queries to inform subsequent ones. While it has long been known that adaptivity can provide an exponential speedup in query complexity for certain properties, this paper explores a more granular question: Does the power of a tester increase incrementally as we allow more "stages" or "rounds" of adaptivity?

This work establishes an adaptivity hierarchy theorem, proving that for any number of rounds $k$, there exist properties that are efficiently testable in $k$ rounds but require exponentially more queries if limited to $k-1$ rounds.

The Concept of Adaptive Rounds

To formalize this hierarchy, the authors define a model of "rounds of adaptivity." In a $k$-round adaptive tester, queries are partitioned into $k$ batches. The queries in round $i$ may depend on the responses received in rounds $1$ through $i-1$.

  • 1-round adaptivity corresponds to non-adaptive testing.
  • Fully adaptive testing allows each query to depend on all previous ones (effectively $q$ rounds for $q$ queries).

The central question is whether $k+1$ rounds are fundamentally more powerful than $k$ rounds. The authors demonstrate that adaptivity is not a binary toggle but a spectrum where each additional round can significantly reduce the query complexity required to test a property.

Methodology: The Lifting Framework

The authors prove the hierarchy theorem using a sophisticated "lifting" approach, which translates lower bounds from simple query models into the more complex property testing setting.

1. Decision Tree Hierarchy

The proof begins in the model of decision trees. The authors define a "$k$-iterated address" function, which is essentially a game of pointer chasing. To determine the final value, an algorithm must follow a chain of $k$ pointers. A $k$-round adaptive algorithm can follow one pointer per round, completing the task with very few queries. However, an algorithm restricted to $k-1$ rounds eventually "gets stuck" and is forced to guess, leading to a massive increase in the number of queries needed to succeed.

2. Lifting to Property Testing via Coding Theory

To move from the decision tree model to property testing, the authors utilize modern coding theory. They employ Locally Testable Codes (LTCs) and relaxed Locally Decodable Codes (LDCs) to "embed" the hard pointer-chasing problem into a functional property. These codes ensure that the property remains robust; if an input is far from having the property, the structure of the code allows a tester to detect this with high probability. This step demonstrates that LTCs and LDCs are not just tools for data transmission but are essential for proving complexity hierarchies.

3. Communication Complexity

For the lower bounds, the authors reduce the testing problem to the "pointer-following" problem in communication complexity. By leveraging established lower bounds in that field, they prove that $k-1$ rounds are insufficient for efficient testing of their constructed properties.

Key Results

The Main Hierarchy Theorem

The paper's primary contribution is the proof that for any $k \le n^{0.99}$, there exists a property $P_{n,k}$ such that:

  • A $k$-round adaptive tester requires only $\tilde{O}(k)$ queries.
  • Any $(k-1)$-round adaptive tester requires $\Omega(n)$ queries.

This represents an exponential gap in query complexity for just a single additional round of adaptivity, confirming a strict hierarchy.

Natural Graph Properties

Beyond engineered properties, the authors investigate whether this hierarchy exists for "natural" problems. They analyze the property of being $(2k+1)$-cycle free in the bounded-degree graph model. They find a similar, though less extreme, gap:

  • $k$ rounds allow for a tester with $O(1/\epsilon)$ queries (independent of the graph size $n$).
  • $k-1$ rounds require $\Omega(\sqrt{n})$ queries.

Discussion and Future Work

While this paper provides a definitive answer to the existence of an adaptivity hierarchy, it opens several new avenues for research. The strongest results rely on properties specifically engineered to prove the theorem ($P_{n,k}$). A significant open question is whether a single property exists that exhibits a multi-level hierarchy—where query complexity drops significantly at every step from 1 to $k$ rounds.

Additionally, while the authors demonstrated a gap for cycle-freeness in graphs, further work is needed to identify other natural properties (such as $m$-linear functions in Boolean function testing) that might exhibit similar sensitivity to the number of adaptive rounds. This research underscores that the amount of sequential dependency in an algorithm is a fundamental bottleneck in sublinear-time computation.

Summary updated

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 n in N and 0 <= k <= n^{0.99} there exists a property Pi_{n,k} of functions for which (1) there exists a k-adaptive tester for Pi_{n,k} with query complexity tilde O(k), yet (2) any (k-1)-adaptive tester for Pi_{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.
BibTeX
@article{canonne2018adaptivity,
  author = {Clément L. Canonne and Tom Gur},
  title = {{An Adaptivity Hierarchy Theorem for Property Testing}},
  journal = {Comput. Complex.},
  year = {2018},
  doi = {10.1007/s00037-018-0168-4},
}
Figure