5 papers
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…
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.…
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…
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…