BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Seminar/Colloquia
DESCRIPTION:Dr. Jeremy Fineman\nAssociate Professor of Computer Science\, G
 eorgetown University\n\nOne of the simplest problems on directed graphs is 
 that of identifying the set of vertices reachable from a designated source 
 vertex. This problem can be solved easily sequentially by performing a grap
 h search\, but efficient parallel algorithms have eluded researchers for de
 cades. For sparse high-diameter graphs in particular\, there is no previous
 ly known parallel algorithm with both nearly linear work and nontrivial par
 allelism. 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 probabilit
 y\, where n is the number of vertices and m is the number of arcs.\n\nThe m
 ain technical contribution is an efficient algorithm that\, through the add
 ition of O(n*polylog(n)) shortcuts\, reduces the diameter of the graph to O
 (n^{2/3}*polylog(n)) with high probability. No efficient sequential or para
 llel algorithms were previously known for this problem.  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 additiona
 l challenges.
DTEND:20211015T170000Z
DTSTAMP:20260414T065216Z
DTSTART:20211015T160000Z
GEO:38.648882;-90.302207
LOCATION:Stephen F. & Camilla T. Brauer Hall\, Brauer 12
SEQUENCE:0
SUMMARY:Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
UID:tag:localist.com\,2008:EventInstance_37995740363175
URL:https://happenings.washu.edu/event/nearly_work-efficient_parallel_algor
 ithm_for_digraph_reachability
END:VEVENT
END:VCALENDAR