Bernhard Haeupler is an Assistant Professor at the Computer Science
Department of Carnegie Mellon University. He received his PhD and MSc in
Computer Science from MIT, and a BSc, MSc and Diploma in (Applied)
Mathematics from the Technical University of Munich. He has
(co-)authored over 70 publications and won several awards for his
research, including STOC and SODA best student paper awards, the 2014
ACM-EATCS Doctoral Dissertation Award of Distributed Computing and the
NSF CAREER award. His research interests lie in the intersection of
classical algorithm design, distributed computing, and coding theory.

AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

MPI Audience

English

60 Minutes

Saarbrücken

Whether or not a distributed optimization problem, such as MST, shortest
path, or min-cut, can be solved fast in a given network depends in a
highly non-trivial manner on the network's topology. While there are
pathological worst-case n-node topologies on which any of these
optimization problems require Omega(sqrt(n)) rounds to compute, despite
a small diameter D, most networks allow for fast O(D polylog n) round
distributed algorithms. This talk will introduce the low-congestion
shortcuts framework which allows to study these dependencies and makes
it easy to design algorithms that, on networks of interest, are provably
fast and often near instance optimal.

This is joint work with Mohsen Ghaffari, Goran Zuzic, Taisuke Izumi,
Ellis Hershkowitz, David Wajc, and Jason Li.

Petra Schaaf

5000

--email hidden

passcode not visible

logged in users only