3 papers
cs.DS2026
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…
cs.DS2025
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,…
cs.CC2024
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…