## CS Colloquium: Valerie King, Department of Computer Science, University of Victoria

**The School of Informatics, Computing, and Engineering (SICE) CS Colloquium Series - Distinguished Speaker Series**

**Speaker: **Valerie King, Department of Computer Science, University of Victoria

**Where:** Luddy Hall, Rm. 1106 (Dorsey Learning Hall)

**When: **Friday, April 26, 2019, 3:00 pm

**Topic:** *The Challenge of Broadcast or How many messages does it take to build a phone tree?*

**Abstract:** The problem of broadcasting in a distributed network is to transmit a single message from one node to every other node. We assume each node knows its neighbors, and communication is by message-passing. For many years, the simple flooding algorithm was considered optimal but this requires a transmission across every edge. Since 2015, there has been substantial progress on this problem. Monte Carlo algorithms, for synchronous and asynchronous networks can build a spanning tree (or minimum spanning tree) with a number of messages sublinear in the number of edges, for dense graphs. But Monte Carlo algorithms have a probability of error. Is a deterministic algorithm possible?

In this talk I’ll focus on recent work about a simplified version of the problem. It has led to a surprising graph sampling lemma and a new method for determining a spanning tree in an MPC model like hadoop or map-reduce.

**Brief bio:** Valerie King is professor of computer science at the University of Victoria in Canada. She received her PhD in computer science and a JD from UC Berkeley. In 2014, she received the distinction of ACM Fellow for her work on randomized algorithms, especially dynamic graph algorithms and Byzantine fault-tolerant distributed computing.

- Start
- Friday April 26, 2019 03:00 PM
- End
- Friday April 26, 2019 04:00 PM
- Contact
- Funda Ergun
- Website
- http://webhome.cs.uvic.ca/~val/
- Contact Email
- fergun@indiana.edu