Online Versus Offline Adversaries in Property Testing

Esty Kelman, Ephraim Linder, Sofya Raskhodnikova

TL;DR

This paper investigates property testing in the face of adversarial data manipulation, comparing "offline" (pre-algorithm) and "online" (during-algorithm) adversaries. They demonstrate that these two adversarial models are incomparable in terms of query complexity and show a significant separation in randomness complexity, with online adversaries often requiring exponentially more random bits.

What Problem Does This Paper Address?

Property testing is a field focused on efficiently verifying if a large dataset possesses a certain property, even when the data might be noisy or incomplete. A key challenge arises when an adversary can manipulate the data. This paper delves into two distinct adversarial models:

  • Offline Adversary: The adversary modifies the data before the testing algorithm begins. This can involve erasing parts of the data (erasures) or altering values (corruptions).
  • Online Adversary: The adversary can manipulate the data during the execution of the testing algorithm, potentially adapting their strategy based on the algorithm's queries. This can also involve erasures or corruptions.

While it might seem intuitive that an online adversary is more powerful, the exact relationship between these models, especially concerning query and randomness complexity, was not fully understood. Specifically, the paper addresses:

  1. Query Complexity Incomparability: Can we find properties that are easier to test against an online adversary than an offline one, or vice-versa?
  2. Randomness Complexity Separation: How much randomness is truly necessary for property testing under these adversarial models, and can we achieve significant savings by using offline adversaries compared to online ones?

Methods

The paper introduces novel techniques and leverages existing results to establish its findings:

  • "Lifting" Operation: A core technique is a method to "lift" a property that is easy to test in the standard model (no adversary) into a property that is testable in the presence of an online adversary. This is achieved by encoding the original property using a repetition code, essentially repeating the input string multiple times. This allows them to transfer existing separations between the standard and offline models to separations between the online and offline models.
  • Reduction from Randomness to Queries: For the randomness complexity results, they develop a reduction that transforms a randomness-efficient tester in the online model into a query-efficient tester in the standard model. This is a key technical contribution that allows them to prove lower bounds on randomness for online testers.
  • Leveraging Existing Results: The authors build upon prior work, particularly results that separate the standard model from offline adversarial models (e.g., [BFLR20]) and results on the randomness complexity of property testing in the standard model ([GS10]).
  • Construction of Specific Properties: To demonstrate the incomparability and separations, they construct specific properties, such as a variant of the "T-Distinct-Elements" property, which are carefully chosen to highlight the differences between the adversarial models.

Datasets

Not discussed in the paper. The focus is on theoretical properties of algorithms and adversarial models, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Incomparability of Adversarial Models: The most striking insight is that neither the online nor the offline adversarial model is strictly more powerful than the other in terms of query complexity. They construct properties where one model requires significantly fewer queries than the other, demonstrating a fundamental difference in their capabilities.
  • The Power of Online Adversaries in Randomness: The paper reveals a substantial gap in randomness complexity. Testing properties against online adversaries can necessitate exponentially more random bits than against offline adversaries, even when the query complexity is comparable. This highlights that online adversaries can be particularly effective at "foiling" randomized algorithms that rely on predictable query patterns.
  • Repetition Codes as a Bridge: The "lifting" technique using repetition codes proves to be a powerful tool for transferring theoretical results and establishing separations between different adversarial models.
  • Randomness is Crucial for Online Adversaries: The work shows that for certain testable properties, sublinear query testers in the online model cannot be significantly derandomized, unlike their offline counterparts. This implies that randomness is inherently more critical when facing an adaptive, online adversary.

Key Results

The paper presents two main categories of results:

Query Complexity Separations:

  • Online Easier than Offline: They construct a property that can be tested with a constant number of queries in the online corruption model, but requires a nearly linear number of queries (Ω(n/polylog n)) in the offline erasure model.
  • Offline Easier than Online (in some cases): While not the primary focus of the separation, they also reference prior work showing properties that are testable with few offline erasures but impossible with online erasures, indicating the incomparability.

Randomness Complexity Separations:

  • Exponential Gap: They demonstrate a property that is testable in both online and offline erasure models with sublinear queries. However, testing this property against an online adversary requires exponentially more random bits (e.g., Ω(√n)) compared to the offline adversary (O(log n)).
  • Generalization: Theorem 4.1 provides a general framework for randomness separations, showing that for various settings of parameters, the online model demands significantly more randomness.

Limitations and Future Work

  • Specific Properties: The separations are demonstrated using specific constructed properties. A natural question is whether these separations hold for a broader class of "natural" properties.
  • Erasure vs. Corruption: While some results extend to corruptions, the primary focus is often on erasures. Further exploration of the interplay between erasures and corruptions in both online and offline settings could be valuable.
  • Open Questions: The paper explicitly mentions an "intriguing open question" about whether there exists a property where an online tester accumulates at least as many erasures as the best offline tester, but requires fewer queries. This remains an active area of research.
  • Practical Implications: While theoretical, these results have implications for designing robust algorithms in scenarios where data is not only large but also subject to adversarial manipulation, guiding choices about query strategies and randomness usage.

Summary updated

Abstract

We study property testing with incomplete or noisy inputs. The models we consider allow for adversarial manipulation of the input, but differ in whether the manipulation can be done only offline, i.e., before the execution of the algorithm, or online, i.e., as the algorithm runs. The manipulations by an adversary can come in the form of erasures or corruptions. We compare the query complexity and the randomness complexity of property testing in the offline and online models. Kalemaj, Raskhodnikova, and Varma (Theory Comput. `23) provide properties that can be tested with a small number of queries with offline erasures, but cannot be tested at all with online erasures. We demonstrate that the two models are incomparable in terms of query complexity: we construct properties that can be tested with a constant number of queries in the online corruption model, but require querying a significant fraction of the input in the offline erasure model. We also construct properties that exhibit a strong separation between the randomness complexity of testing in the presence of offline and online adversaries: testing these properties in the online model requires exponentially more random bits than in the offline model, even when they are tested with nearly the same number of queries in both models. Our randomness separation relies on a novel reduction from randomness-efficient testers in the adversarial online model to query-efficient testers in the standard model.
BibTeX
@inproceedings{kelman2025online,
  author = {Esty Kelman and Ephraim Linder and Sofya Raskhodnikova},
  title = {{Online Versus Offline Adversaries in Property Testing}},
  booktitle = {ITCS},
  year = {2025},
  url = {https://openreview.net/forum?id=Ce7K14Yyhz},
}
Figure