Barriers due to Congestion and Two Ways to Deal With Them
Restricting the bandwidth in models of distributed graph computations naturally introduces challenges that arise due to communication bottlenecks. In this talk, I will survey techniques for proving lower bounds on the complexity of fundamental graph problems under limited bandwidth. For some problems, allowing relaxed solutions can significantly reduce the required amount of communication, enabling efficient computations. Two successful approaches for overcoming provable barriers, namely, approximations and testing, will be exemplified and discussed in the context of distributed computing.
Keren Censor-Hillel is an associate professor in the Department of Computer Science at the Technion. She completed her Ph.D. dissertation at the Technion in 2010, for which she received the Principles of Distributed Computing Doctoral Dissertation Award. Afterward, she was a Simons Postdoctoral Fellow in the Computer Science and Artificial Intelligence Lab at MIT. She is a recipient of an Alon Fellowship awarded by the Israeli Academy of Science in 2013 and a Krill Prize awarded by the Wolf Foundation in 2016. She was recently awarded an ERC Starting Grant. Her research focuses on the theory of distributed computing.