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

11月26日  14:00--15:00

Speaker

Gregory Schwartzman received his PhD from the Technion, Israel, in 2017. Since then he has been a postdoc at the National Institute of Informatics, Tokyo.

His research deals with designing fast algorithms for fundamental graph problems in environments with uncertainty, specifically distributed algorithms. His works were awarded with the best student paper award at PODC 2016 and best paper and best student paper award at SODA 2017.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号