Seminar Details

In the semi-streaming model, an algorithm must process any $n$-vertex graph by making one or few passes over a stream of its edges using $O(n \text{poly }\log(n))$ words of space, and at the end of the last pass, output a solution to the problem of interest. We focus on approximating the shortest path distance between two known vertices $s$ and $t$, and make progress on this question from both directions.

We give a simple randomized $(1+\epsilon)$-approximation algorithm for any $\epsilon > 0$ which runs in $O( (n/\epsilon) \cdot \log^3(n))$ space and $O((1/\epsilon) \cdot \log^2(n))$ passes. Prior to our work, the best known algorithms used $O((1/\epsilon) \cdot \log^c(n))$ passes for some large unspecified constant $c$.

We also give a lower bound that any algorithm estimating the distance between $s, t$ up to any constant approximation factor requires $\Omega(\log n/\log \log n)$ passes over the edges in semi-streaming. Previously, only constant-pass lower bounds were known and only for small approximation ratios below two. In this talk, however, we only focus on the upper bound result.

Joint work with Sepehr Assadi and Gary Hoppenworth.