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