23 citations · 39 across the 15 of their papers we have counts for
33 papers
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…
Is this correct? Let's check!
Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel +1
Societal accumulation of knowledge is a complex process. The correctness of new units of knowledge depends not only on the correctness of new reasoning, but also on the correctness…
Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions
Omri Ben-Eliezer, Dan Mikulincer, Ilias Zadik
The last few years have seen a surge of work on high dimensional statistics under privacy constraints, mostly following two main lines of work: the ``worst case'' line, which does…
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…
Active Learning Polynomial Threshold Functions
Omri Ben-Eliezer, Max Hopkins, Chutong Yang +1
We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially activel…
Sampling Multiple Nodes in Large Networks: Beyond Random Walks
Omri Ben-Eliezer, Talya Eden, Joel Oren +1
Sampling random nodes is a fundamental algorithmic primitive in the analysis of massive networks, with many modern graph mining algorithms critically relying on it. We consider the…
What is Learned in Knowledge Graph Embeddings?
Michael R. Douglas, Michael Simkin, Omri Ben-Eliezer +4
A knowledge graph (KG) is a data structure which represents entities and relations as the vertices and edges of a directed graph with edge types. KGs are an important primitive in…
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…
Information Spread with Error Correction
Omri Ben-Eliezer, Elchanan Mossel, Madhu Sudan
We study the process of information dispersal in a network with communication errors and local error-correction. Specifically we consider a simple model where a single bit of infor…
Learning Multimodal Affinities for Textual Editing in Images
Or Perel, Oron Anschel, Omri Ben-Eliezer +2
Nowadays, as cameras are rapidly adopted in our daily routine, images of documents are becoming both abundant and prevalent. Unlike natural images that capture physical objects, do…
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
Noga Alon, Omri Ben-Eliezer, Yuval Dagan +3
Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We…
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…
Hard properties with (very) short PCPPs and their applications
Omri Ben-Eliezer, Eldar Fischer, Amit Levi +1
We show that there exist properties that are maximally hard for testing, while still admitting PCPPs with a proof size very close to linear. Specifically, for every fixed , w…
READ: Recursive Autoencoders for Document Layout Generation
Akshay Gadi Patil, Omri Ben-Eliezer, Or Perel +1
Layout is a fundamental component of any graphic design. Creating large varieties of plausible document layouts can be a tedious task, requiring numerous constraints to be satisfie…
Very fast construction of bounded-degree spanning graphs via the semi-random graph process
Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz +1
Semi-random processes involve an adaptive decision-maker, whose goal is to achieve some predetermined objective in an online randomized environment. They have algorithmic implicati…
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…
The hat guessing number of graphs
Noga Alon, Omri Ben-Eliezer, Chong Shangguan +1
Consider the following hat guessing game: players are placed on vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of possible colors.…