4 papers · 1 filter
Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
Alexandr Andoni, Themistoklis Haris, Esty Kelman +1
We study the Approximate Nearest Neighbor (ANN) problem under a powerful adaptive adversary that controls both the dataset and a sequence of queries. Primarily, for the high-di…
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,…
Online versus Offline Adversaries in Property Testing
Esty Kelman, Ephraim Linder, Sofya Raskhodnikova
We study property testing with incomplete or noisy inputs. The models we consider allow for adversarial manipulation of the input, but differ in whether the manipulation can be don…
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…