Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

In this talk I'll present a new paper from Jeremy Fineman on parallel algorithms for directed graph reachability. (arXiv:1711.01700). This paper reopens the "transitive closure bottleneck" question that bedeviled parallel algorithms researchers in the 1980s and 90s.