Special Theory Seminar

Thursday, July 5, 2018 - 2:00pm to 3:00pm


Blelloch-Skees Conference Room 8115 Gates Hillman Centers


JEREMY T. FINEMAN, Associate Professor, Wagner Term Chair in Computer Science http://people.cs.georgetown.edu/~jfineman/

One of the simplest problems on directed graphs is that of identifying the set of vertices reachable from a specified source vertex. This problem can be solved sequentially by performing a graph search, but efficient parallel algorithms have eluded researchers for decades. For sparse high-diameter graphs in particular, there is no previously known parallel algorithm with both nearly linear work and nontrivial parallelism. This talk presents the first such algorithm. Specifically, this talk presents a randomized parallel algorithm for digraph reachability with work O(m*polylog(n)) and span O(n^{2/3}*polylog(n)), with high probability, where n is the number of vertices and m is the number of arcs.

The main technical contribution is an efficient Monte Carlo algorithm that, through the addition of O(n*polylog(n)) shortcuts, reduces the diameter of the graph to O(n^{2/3}*polylog(n)) with high probability. While there are existing algorithms that achieve similar guarantees, they are not efficient; the sequential algorithms have running times much worse than linear. This talk presents a surprisingly simple sequential algorithm with running time O(m log^2(n)) that achieves the stated diameter reduction. Parallelizing that algorithm yields the main result, but doing so involves overcoming several additional challenges.

Faculty Host: Guy Blelloch

For More Information, Contact:


Special Seminar