1.7k citations · 1.9k across the 33 of their papers we have counts for
3 papers · 1 filter
How Hard is Counting Triangles in the Streaming Model
Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik
The problem of (approximately) counting the number of triangles in a graph is one of the basic problems in graph theory. In this paper we study the problem in the streaming model.…
Local Correctability of Expander Codes
Brett Hemenway, Rafail Ostrovsky, Mary Wootters
In this work, we present the first local-decoding algorithm for expander codes. This yields a new family of constant-rate codes that can recover from a constant fraction of errors…
Secure End-to-End Communication with Optimal Throughput in Unreliable Networks
Paul Bunn, Rafail Ostrovsky
We demonstrate the feasibility of end-to-end communication in highly unreliable networks. Modeling a network as a graph with vertices representing nodes and edges representing the…