23 citations · 39 across the 15 of their papers we have counts for
16 papers · 1 filter
Collision Detection is Instance ptimal Under the Birthday Threshold
Omri Ben-Eliezer, Tomer Grossman, Václav Rozhoň +1
Can structural knowledge about a hash function help accelerate the (black box) detection of collisions in it? This question is fundamental to cryptography theory given the importan…
Robust Streaming Against Low-Memory Adversaries
Omri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal
Robust streaming, the study of streaming algorithms that provably work when the stream is generated by an adaptive adversary, has seen tremendous progress in recent years. However,…
Approximate counting of permutation patterns
Omri Ben-Eliezer, Slobodan Mitrović, Pranjal Srivastava
We consider the problem of counting the copies of a length- pattern in a sequence , where a copy is a subset of indices $i_1 < \ldots < i_k \in…
A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
Sabyasachi Basu, Nadia Kōshima, Talya Eden +2
Computing distances and finding shortest paths in massive real-world networks is a fundamental algorithmic task in network analysis. There are two main approaches to solving this t…
On the instance optimality of detecting collisions and subgraphs
Omri Ben-Eliezer, Tomer Grossman, Moni Naor
Suppose you are given a function via (black-box) query access to the function. You are looking to find something local, like a collision (a pair s.…
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…
Bounded Space Differentially Private Quantiles
Daniel Alabi, Omri Ben-Eliezer, Anamay Chaturvedi
Estimating the quantiles of a large dataset is a fundamental problem in both the streaming algorithms literature and the differential privacy literature. However, all existing priv…
Adversarially Robust Streaming via Dense--Sparse Trade-offs
Omri Ben-Eliezer, Talya Eden, Krzysztof Onak
A streaming algorithm is adversarially robust if it is guaranteed to perform correctly even in the presence of an adaptive adversary. Recently, several sophisticated frameworks for…
A Framework for Adversarially Robust Streaming Algorithms
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff +1
We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chose…
Optimal Adaptive Detection of Monotone Patterns
Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten
We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed and , consider the problem of findi…
Finding monotone patterns in sublinear time
Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter +1
We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed and , we show that the n…
The Adversarial Robustness of Sampling
Omri Ben-Eliezer, Eylon Yogev
Random sampling is a fundamental primitive in modern algorithms, statistics, and machine learning, used as a generic method to obtain a small yet "representative" subset of the dat…
Testing local properties of arrays
Omri Ben-Eliezer
We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of -dimensional arrays is -local if it can be defined by a fa…
Earthmover Resilience and Testing in Ordered Structures
Omri Ben-Eliezer, Eldar Fischer
One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and…
Improved Bounds for Testing Forbidden Order Patterns
Omri Ben-Eliezer, Clément L. Canonne
A sequence contains a permutation of length if there exist such that, for all , if and only if $π(x…
Testing hereditary properties of ordered graphs and matrices
Noga Alon, Omri Ben-Eliezer, Eldar Fischer
We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary p…