Please note: This PhD seminar will take place in DC 1304 and online.
Janani Sundaresan, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Sepehr Assadi
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.
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.