Over the last decade, there has been considerable interest in designing algorithms for
processing massive graphs in the data stream model. The original motivation was two-fold …

When processing massive data sets, a core task is to construct synopses of the data. To be
useful, a synopsis data structure should be easy to construct while also yielding good …

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 …

Any graph with maximum degree Δ admits a proper vertex coloring with Δ+ 1 colors that can
be found via a simple sequential greedy algorithm in linear time and space. But can one find …

Graph clustering is a fundamental task in many data-mining and machine-learning
pipelines. In particular, identifying a good hierarchical structure is at the same time a …

The dynamic graph connectivity problem is the following: given a graph on a fixed set of n
nodes which is undergoing a sequence of edge insertions and deletions, answer queries of …

There is a rapidly growing need for scalable algorithms that solve classical graph problems,
such as maximum matching and minimum vertex cover, on massive graphs. For massive …

We present the first single pass algorithm for computing spectral sparsifiers for graphs in the
dynamic semi-streaming model. Given a single pass over a stream containing insertions and …

We present a general framework for constructing cut sparsifiers in undirected graphs---
weighted subgraphs for which every cut has the same weight as the original graph, up to a …

While there has been a tremendous interest in processing data that has an underlying graph
structure, existing distributed graph processing systems take several minutes or even hours …