Alice and Bob Walked into a Graph...

9^th March 2023, 15:00 Ashton Lecture Theatre
Dr. Sagnik Mukhopadhyay
Department of Computer Science, University of Sheffield

Abstract

I will talk about simple algorithms for cut and flow problems in the 2-party communication setting that can be adapted to many other distributed models of computation quickly. In the realm of data explosion, it is usually the case that a single computational processor is unable to store the vast amount of data needed to do any meaningful computation. We are indeed in the era of distributed computing, but it is not ideal to have different ad-hoc 'model-dependent' algorithms for solving the same problem. I will show recent progress in designing cross-paradigm algorithms that tackle this issue.

I will show two examples: the minimum-cut problem (or min-cut) and the maximum bipartite matching problem (or BMM) where, in each case, a simple schematic algorithm can be implemented in a number of computational models to achieve the optimal complexity. This is a culmination of a number of papers that appeared in the last couple of years with coauthors Joakim Blikstad, Jan van den Brand, Yuval Efron, Troy Lee, Simon Apers, Pawel Gawrychowski, Michal Dory, Andrés López-Martínez and Danupon Nanongkai.