EE Seminar: MST in Log-Star Rounds of Congested Clique

~~ (The talk will be given in English)

Speaker:  Dr. Merav Parter
                         MIT

Sunday, May 1st, 2016
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering

MST in Log-Star Rounds of Congested Clique

Abstract
We present a randomized algorithm that computes a Minimum Spanning Tree (MST) in O(log^* n) rounds, with high probability, in the Congested Clique model of distributed computing. In this model, the input is a graph on n nodes, initially each node knows only its incident edges, and per round each two nodes can exchange O(log n) bits.
Our key technical novelty is an O(log^* n) Graph Connectivity algorithm, the heart of which is a (recursive) forest growth method, based on a combination of two ideas: a sparsity-sensitive sketching aimed at sparse graphs and a random edge sampling aimed at dense graphs.
Our result improves significantly over the $O(\log \log \log n)$ algorithm of Hegeman et al. [PODC 2015] and the $O(\log \log n)$ algorithm of Lotker et al. [SPAA 2003; SICOMP 2005].
This join work with Mohsen Ghaffari, MIT, CSAIL.

Bio: Merav Parter is a Postdoctoral Fellow at MIT hosted by Prof. Nancy Lynch. She received a Ph.D. degree in Computer Science from the Weizmann Institute of Science under the guidance of Prof. David Peleg.
Her thesis "The Topology of Wireless Communication and Applications" won the first place Feder prize award for best student work in communication technology. Parter is a Rothschild and Fulbright Fellow.
In the past, she was a Google European Fellow in Distributed Computing, 2012. Her research interests focus on two aspects of reliable communication: fault tolerant graph structures and wireless communication. She's particularly intrigued with bridging the gap between Electrical Engineering and Theoretical Computer Science.

 

01 במאי 2016, 15:00 
חדר 011, בניין כיתות-חשמל 
אוניברסיטת תל אביב עושה כל מאמץ לכבד זכויות יוצרים. אם בבעלותך זכויות יוצרים בתכנים שנמצאים פה ו/או השימוש
שנעשה בתכנים אלה לדעתך מפר זכויות, נא לפנות בהקדם לכתובת שכאן >>