The Taub Faculty of Computer Science Events and Talks

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.