דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Distance Computation in Distributed Networks
event speaker icon
מיכל דורי, הרצאה סמינריונית לדוקטורט
event date icon
יום רביעי, 24.6.2020, 14:30
event location icon
Zoom Lecture: https://technion.zoom.us/j/99489358773
event speaker icon
מנחה:  Prof. Keren Censor-Hillel
In this talk, I will describe a couple of results from my PhD thesis, that studies distributed algorithms for connectivity and distance related graph problems. I will focus on a recent line of work studying distance computation in the Congested Clique model of distributed computing. We design fast algorithms for the fundamental all-pairs shortest paths (APSP) and multi-source shortest paths (MSSP) problems. In particular, we show constant-factor approximation algorithms for weighted APSP and MSSP that take just poly-logarithmic time. Moreover, in unweighted graphs, we solve the same problems much faster, in just poly(loglogn) time. All previous algorithms require at least a polynomial number of rounds. Our main techniques are new distance tools we develop, based on sparse matrix multiplication, and a new fast construction of a near-additive emulator, a sparse graph that preserves the distances of the original graph up to a near-additive stretch. Based on joint works with Keren Censor-Hillel, Janne H Korhonen, Dean Leitersdorf, and Merav Parter.
[בחזרה לאינדקס האירועים]