Fundamental Graph Algorithms for Distributed Networks (Gregory Schwartzman)

Abstract

In this talk I will describe two lines of research which I’ve followed for the past few years. The main focus of the talk will be recent advances in distributed approximation algorithms for fundamental optimization problems such as Minimum Vertex Cover, Maximum Matching and many more. These problems have been studied for decades in the sequential setting, and are considered to be well understood. The distributed setting presents new challenges, and only recently we have introduced new techniques which allowed us to design optimal algorithms for many of these problems. Our techniques are simple and general, and so apply also to other computational environments, such as the streaming model.

In the second part of the talk, I will review new sub-fields of distributed computing, such as distributed property testing and distributed parametrized graph algorithms. Finally, I will discuss distributed algorithms in highly dynamic networks.

Time

Speaker

Room