In the semi-streaming model for processing massive graphs, an algorithm makes multiple
passes over the edges of a given n-vertex graph and is tasked with computing the solution to …

We prove that any semi-streaming algorithm for (1+ε) approximation of maximum bipartite
matching requires Ω\left (\log (1/ε)\log (1/β)\right) passes, where β∈(0,1) is the largest …

Consider the following 2-respecting min-cut problem. Given any weighted graph G and its
spanning tree T, find the minimum cut among the cuts that contain at most two edges in T …

Recent Advances in Multi-Pass Graph Streaming Lower Bounds Page 1 Recent Advances in
Multi-Pass Graph Streaming Lower Bounds Sepehr Assadi Cheriton School of Computer …

We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and
property testing problems such as estimating the size of maximum matchings and maximum …

We prove that any two-pass graph streaming algorithm for the st reachability problem in n-
vertex directed graphs requires near-quadratic space of n 2-o (1) bits. As a corollary, we also …

Consider the following gap cycle counting problem in the streaming model: The edges of a 2-
regular n-vertex graph G are arriving one-by-one in a stream and we are promised that G is …

We prove a lower bound on the space complexity of two-pass semi-streaming algorithms
that approximate the maximum matching problem. The lower bound is parameterized by the …

In the experts problem, on each of T days, an agent needs to follow the advice of one of n
“experts”. After each day, the loss associated with each expert's advice is revealed. A …

We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up
to polylogarithmic factors in five models of computation: the two-party communication, AND …