Simons Institute | Property Testing with Incomplete or Manipulated Inputs @SimonsInstituteTOC | Uploaded 1 week ago | Updated 14 hours ago
Sofya Raskhodnikova
https://simons.berkeley.edu/talks/sofya-raskhodnikova-2024-08-05
Workshop on Local Algorithms (WoLA)
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., ＜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.
Home
The Simons Institute for the Theory of Computing is the world's leading venue for collaborative research in theoretical computer science.
Footer
Sofya Raskhodnikova
https://simons.berkeley.edu/talks/sofya-raskhodnikova-2024-08-05
Workshop on Local Algorithms (WoLA)
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., ＜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.
Home
The Simons Institute for the Theory of Computing is the world's leading venue for collaborative research in theoretical computer science.
Footer
