Erasure-Resilient Property Testing

21 concepts4 papers1 proposal

Property testing focuses on a deceptively simple question: can we determine if a massive dataset satisfies a global property (such as monotonicity or convexity) by inspecting only a tiny, sublinear fraction of the data?

In the standard model of property testing, algorithms assume unhindered access to any data point they choose to query. However, real-world data is rarely perfect. Values can be lost during transmission, sensors can fail, or an adversary might strategically hide information. If an algorithm relies on querying specific, highly informative data points, a clever adversary can render the algorithm useless simply by erasing those points.

To address this vulnerability, researchers developed a framework that introduces adversarial data loss into sublinear algorithms, establishing a rich hierarchy of robustness between standard testing, erasure-resilience, and error-tolerance.

The Model: Testing Under Adversarial Erasure

To formalize robustness against missing data, Dixit et al. introduced the concept of erasure-resilient property testing. In this model, the testing process is framed as a game against an adversary who knows the property being tested. Before the testing algorithm begins, the adversary is allowed to hide or "erase" a constant fraction $\alpha$ of the input data.

When the algorithm attempts to query a data point, it interacts with an oracle. If the queried point is intact, the oracle returns its true value; if the adversary has hidden it, the oracle returns a special erasure symbol ($\bot$). The algorithm must still successfully determine whether the underlying function possesses the property or is far from it, using a sublinear number of queries.

This adversarial framing exposes a fundamental complexity gap. Standard property testers often rely on rigid, localized structures. For example, to test if a function is monotonic (always increasing), a standard tester might pick random pairs of adjacent points $(x, y)$ and check if $f(x) \le f(y)$. If an adversary knows this, they can strategically erase one point from every critical pair, forcing the tester to waste queries on incomplete pairs.

Consequently, Dixit et al. demonstrated that certain properties that are easily testable with a constant number of queries in the standard model suddenly require exponentially more queries when even a small fraction of the data is hidden. For more resilient properties like monotonicity and convexity, however, the authors designed specialized testers where the query complexity overhead scales gracefully, typically by a factor proportional to $1/(1-\alpha)$.

Erasures vs. Errors: A Fundamental Separation

When data is imperfect, it generally suffers from one of two flaws: it is either missing (an erasure) or corrupted (an error). Intuitively, dealing with corrupted data—known as tolerant property testing—feels more difficult. A corrupted data point actively misleads an algorithm by presenting an incorrect value as truth, whereas an erasure honestly declares itself as missing.

This intuition was formalized into a strict mathematical hierarchy by Raskhodnikova and Varma, who proved that handling missing data is fundamentally easier than handling corrupted data. They established a formal separation between the two models by demonstrating the existence of properties that can be efficiently verified with a sublinear number of queries under adversarial erasures, but become completely intractable—requiring query complexities that grow with the total input size—when the data contains errors.

  [ Standard Property Testing ] 
               │  (Easiest: Full access to all queries)
               ▼
  [ Erasure-Resilient Testing ] 
               │  (Intermediate: Adversary hides data; algorithm knows what is missing)
               ▼
  [ Tolerant Property Testing ] 
                  (Hardest: Adversary corrupts data; algorithm is actively misled)

Why does this gap exist? As Raskhodnikova et al. later showed, the hardness of tolerant testing is deeply tied to the intrinsic complexity of underlying computational problems, such as Boolean formula satisfiability. Because an erasure explicitly tells the algorithm where information is missing, the algorithm can dynamically adapt or navigate around the gaps. An error, by contrast, forces the algorithm to implicitly solve a noisy decoding problem, making it significantly harder to distinguish true underlying structure from malicious noise.

A Bridge for Proving Lower Bounds

Beyond its utility in designing robust algorithms, the erasure-resilient framework has emerged as a powerful mathematical tool for proving the limits of standard property testers.

Consider nonadaptive testers—algorithms that must select all of their query points simultaneously before observing any of the oracle's answers. Proving tight lower bounds on how well these algorithms can approximate function properties (such as a function's distance to monotonicity) is notoriously difficult.

Pallavoor et al. recognized that the uncertainty an algorithm faces when encountering adversarial erasures mathematically mirrors the uncertainty a nonadaptive algorithm faces when trying to sample a function blindly. By proving hardness bounds within the erasure-resilient model, the authors successfully established a formal bridge to the standard model. This technique allowed them to settle a long-standing open question, yielding a tight lower bound for nonadaptively approximating the distance to monotonicity for Boolean functions.

Key Foundational Work

Erasure-Resilient Property Testing (2018) — contributed 8 concept elements to this direction.
Brief Announcement: Erasure-Resilience Versus Tolerance to Errors (2018) — contributed 7 concept elements to this direction.
Erasure-Resilient Property Testing (2016) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_separation_of_erasure_resilient_and_tole_dd09e522,
  title = {separation of erasure-resilient and tolerant property testing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/separation-of-erasure-resilient-and-tolerant-property-testing/rdr_dd09e52242884ef2804d8f2ee928a3df},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_separation_of_erasure_resilient_and_tole_dd09e522_v1,
  title = {separation of erasure-resilient and tolerant property testing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/separation-of-erasure-resilient-and-tolerant-property-testing/rdr_dd09e52242884ef2804d8f2ee928a3df/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake