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. 121223 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 nontrivial 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 sublinear 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 YiJun 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.
