BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Clifford Stein (Coumbia University) DTSTART:20200618T170000Z DTEND:20200618T180000Z DTSTAMP:20260423T021018Z UID:TCSPlus/8 DESCRIPTION:Title: Parallel approximate undirected shortest paths via low hop emulators\n by Clifford Stein (Coumbia University) as part of TCS+\n\n\nAbstract\nAlth ough sequential algorithms with (nearly) optimal running time for finding shortest paths in undirected graphs with non-negative edge weights have be en known for several decades\, near-optimal parallel algorithms have turne d out to be a much tougher challenge. In this talk\, we present a $(1+\\va repsilon)$-approximate parallel algorithm for computing shortest paths in undirected graphs\, achieving polylog depth and near-linear work. All prio r $(1+\\varepsilon)$-algorithms with polylog depth perform at least super linear work. Improving this long-standing upper bound obtained by Cohen (S TOC'94) has been open for 25 years.\n\nOur algorithm uses several new tool s. Prior work uses hopsets to introduce shortcuts in the graph. We introdu ce a new notion that we call low hop emulators. We also introduce compres sible preconditioners\, which we use in conjunction with Serman's framewor k (SODA '17) for the uncapacitated minimum cost flow problem.\n\nJoint wor k with Alex Andoni and Peilin Zhong.\n\nRescheduled to 06/18/2020 (origina lly scheduled for the 06/10/2020).\n LOCATION:https://researchseminars.org/talk/TCSPlus/8/ END:VEVENT END:VCALENDAR