Friday, February 26, 2016 - 1:00pm to 2:30pm

Location:

32-G631

Speaker:

Mohsen Ghaffari and Hsin-Hao Su

Biography:

MIT

Seminar group:

- Given an arbitrary n-node network G, how can we efficiently simulate one round of the congested clique K_n in G, i.e., how can we deliver one O(log n)-bit message from each node to each other node? This would provide a black-box method for transforming congested clique algorithms to algorithms for more general networks.

- How can we design efficient graph algorithms for networks that are sparse approximations of the clique (expanders), e.g., networks with edge-expansion at least 1/polylog n and maximum degree at most polylog n. We specifically show distributed algorithms with round complexity of 2^{O(sqrt{log n log log n})} for problems such as Minimum Spanning Trees and Minimum Cut.