Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Fast Distributed Optimization Algorithms via Low-Congestion Shortcuts
Speaker:Bernhard Häupler
coming from:Carnegie Mellon University
Speakers Bio: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.
Event Type:INF Distinguished Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Language:English
Date, Time and Location
Date:Tuesday, 13 February 2018
Time:15:15
Duration:60 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Petra Schaaf
Phone:5000
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Petra Schaaf, 01/29/2018 12:17 PM -- Created document.