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, Kolkata, India 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, UK 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.

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node $u$ of degree $d(u)$ is assigned a palette of $d(u)+1$ colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list coloring problem is a natural generalization of the classical $(\Delta+1)$-coloring and $(\Delta+1)$-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing. In this paper we settle the complexity of the (degree+1)-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.

This is based on a joint work with Sam Coy, Artur Czumaj, and Peter Davies

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only