Speaker

Sriram Pemmaraju

Abstract

An important resource in distributed computation is the volume of information that needs to travel between different processors. Efficient distributed algorithms aim to keep this volume, also known as the \textit{message complexity}, as low as possible. The focus of this talk will be the message complexity of distributed algorithms for classical graph optimization problems such as minimum vertex cover (MVC). I will show a strong separation between the message complexity of algorithms that \textit{exactly} solve MVC versus algorithms that \textit{approximately} solve MVC. Specifically, I will prove that any algorithm that solves MVC exactly requires \Omega(n^3) messages, whereas if we allow even an arbitrarily small approximation in the solution, MVC can be solved using O(n^2) messages.

Even though most of the talk will involve a "hardness" proof, I will try to keep the talk accessible to a broad CS audience, highlighting some "gems" of theoretical computer science along the way.

Bio

Sriram V. Pemmaraju is a Professor in the Department of Computer Science at the University of Iowa. He works on graph problems in a distributed setting, focusing on the interplay between computation, communication, randomness, and approximation from a theoretical point of view. He also does applied research, focusing on the use of algorithmic approaches to model and mitigate healthcare associated infections. He briefly met Paul Erdös as a graduate student, but did not have the gumption to initiate a joint project. As a result, his Erdös number is permanently stuck at 2!