2 citations · 2 across the 5 of their papers we have counts for
8 papers
Forbidden Intersection Theorems for Matrix Spaces
Esty Kelman, Nathan Lindzey, Ohad Sheinfeld
A family of matrices is {-intersection-free} if for all . A \em…
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…
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…
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…
Sparse graph counting and Kelley-Meka bounds for binary systems
Yuval Filmus, Hamed Hatami, Kaave Hosseini +1
In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. In thi…