Seminar Announcement
Date: Tuesday, 12 December 2023
Time: 11:30 AM
Venue: Seminar Hall
On Coloring problems in Congested Clique and MPC
Gopinath Mishra
NUS.
12-12-23

---

Abstract

Graph coloring problems are among the most extensively studied problems in the area of distributed graph algorithms. The inherent interaction between the local and global aspects of the coloring problems makes them representative of a variety of problems in distributed settings. In the distributed graph coloring problem, we are given an undirected graph, and we want to color the nodes of it such that no edge is monochromatic. The most fundamental graph coloring problem in distributed computing is the (Delta+1)-coloring problem, where Delta is the maximum degree of any node in the graph. This problem can be easily solved by a sequential greedy algorithm, but the interaction between the local and global aspects of graph coloring creates some non-trivial challenges in a distributed setting. The problem has been used as a benchmark and at the very core of the area of distributed graph algorithms. A generalization of (Delta+1)-coloring is the (Degree+1)-list coloring (D1LC) problem which is more challenging to solve in the distributed models. In this talk, we discuss the results of coloring problems in distributed computing and Massively Parallel Computation (MPC) models with a focus on some recent developments in the (Degree+1)-list coloring (D1LC) problem in Congested Clique and sub-linear MPC.

This is based on two joint works with Sam Coy, Artur Czumaj, and Peter Davies.

Short Bio: Gopinath Mishra is a Post Doctoral Fellow at the National University of Singapore (NUS) hosted by Yi-Jun Chang. He received his Ph. D. from Indian Statistical Institute where he was advised by Arijit Bishnu and Arijit Ghosh. Prior to joining NUS, he was a Post Doctoral Fellow at the University of Warwick hosted by Artur Czumaj. Gopinath's broad research interests are in Theoretical Computer Science with a focus on Model Centric Computation and Algorithms for Big data. In particular, he is interested in Property testing / Query complexity, Streaming, Massively Parallel Computation (MPC) and Distributed Computing, and Distribution Testing.