BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230414T120000Z
UID:57b1e74c65404b70a2d8fd91148cc1c9-446
DTSTAMP:19700101T120011Z
DESCRIPTION:Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/446/hop-constrained-expander-decompositions-oblivious-routing-and-distributed-universal-optimality/
SUMMARY:In a recent result Häupler, Ghaffari, and Zuzic [STOC 2021] showed that so-called   h -hop oblivious routing schemes with a polylogarithmic competitive ratio exist. These can be used to solve packet routing problems almost optimally, i.e., with only a polylogarithmic loss in routing time compared to a globally optimal solution.   

In this talk we present a different way of constructing h -hop oblivious routing schemes that have a weaker (sub-polynomial) competitive ratio but which can be constructed very efficiently by a distributed algorithm.   

This result has important consequences in the area of distributed computing: it gives novel CONGEST algorithms for a large class of important optimization problems, including minimum-spanning tree, ( 1 + ϵ )-min-cut,  ( 1 + ϵ )-shortest paths. Our algorithms solve these problems in sub-polynomial rounds on any network, as long as a sub-polynomial-round distributed algorithm exists for this network.   

This is joint work with Bernhard Häupler and Mohsen Ghaffari. 



Microsoft teams link: 
 
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, Rahul Madhavan, Aditya Subramanian and Aditya Abhay Lonkar
DTSTART:20230414T120000Z
END:VEVENT
END:VCALENDAR