Theory Seminar

Constant Time Coloring in the Congested Clique

Yufan Zheng

Friday, December 07, 2018
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

Given an undirected graph of degree D, a simple linear-time greedy algorithm guarantees that it has a (D+1)-vertex coloring. However, if one considers solving the coloring problem in the distributed setting, it becomes meaningful to optimize the complexity of the algorithm. In this talk, I will present an O(1)-time algorithm for (D+1)-vertex coloring in the CONGESTED-CLIQUE model. In order to obtain this asymptotically optimal algorithm, we exploit the existence of a fast coloring algorithm in the LOCAL model. This CONGESTED-CLIQUE algorithm, along with our results in other models, gives a good example that several distributed computing model (e.g., including LOCAL, LCA, MPC, CONGEST and CONGESTED-CLIQUE) are closely related, by demonstrating that an algorithm in one model often helps us develop an algorithm in another model. Joint work with Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari and Jara Uitto. Manuscript available at: https://arxiv.org/abs/1808.08419.

Additional Information

Sponsor(s): Theory Group

Faculty Sponsor: Seth Pettie

Open to: Public