(Δ + 1) Vertex Coloring in O(n) communication

Speaker:
Organiser:
Hari Krishnan P A
Date:
Friday, 5 Jul 2024, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
Abstract

I will talk about the communication complexity of (Δ+1) vertex coloring, where the edges of an n-vertex graph of maximum degree Δ are partitioned between two players. I will show a randomized protocol which uses O(n) bits of communication and ends with both players knowing the coloring. Combined with a folklore Ω(n) lower bound, this settles the randomized communication complexity of (Δ+1)-coloring up to constant factors.
Based on joint work with Maxime Flin.