Special Theory Seminar
— 3:00pm
Location:
Blelloch-Skees Conference Room 8115
-
Gates Hillman Centers
Speaker:
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:
jennsbl@cs.cmu.edu