4 papers
Optimal Testing of Reed-Muller Codes with an Online Adversary
Esty Kelman, Uri Meir, Kai Zhe Zheng
Motivated by applications to property testing in the online-erasure model of Kalemaj, Raskhodnikova, and Varma (ITCS 2022 and Theory of Computing 2023), we define and analyze {\em…
Homomorphism Testing with Resilience to Online Manipulations
Esty Kelman, Uri Meir, Debanuj Nayak +1
A central challenge in property testing is verifying algebraic structure with minimal access to data. A landmark result addressing this challenge, the linearity test of Blum, Luby,…
On Optimal Testing of Linearity
Vipul Arora, Esty Kelman, Uri Meir
Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about linearity testing in order to resolve two…
Property Testing with Online Adversaries
Omri Ben-Eliezer, Esty Kelman, Uri Meir +1
The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where…