Abstract
What can property testers do when their input is manipulated by an online adversary? We will discuss the model of testing with online adversaries, which extends and complements the study of tolerant testers initiated by Parnas, Ron, and Rubinfeld (J. Comput. Syst., <https://url.au.m.mimecastprotect.com/s/vEVqC6XQ4LfVqR0Equp24Uw?domain=dblp.org> 2006). In this model, sublinear-time algorithms access their input via an online adversarial erasure (or corruption) oracle. After answering each input query, such an oracle can erase (or corrupt) $t$ input values. We will discuss the complexity of fundamental computational tasks in this model and its relationships to offline property testing models.
Based on joint works with Iden Kalemaj and Nithin Varma; Omri Ben-Eliezer, Esty Kelman, and Uri Meir; Esty Kelman and Ephraim Linder.