BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1442
DTSTAMP:20240704T065450Z
SUMMARY:(Δ + 1) Vertex Coloring in O(n) communication
DESCRIPTION:Speaker: Parth Mittal (University of Waterloo)\n\nAbstract: \nI
  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) bit
 s of communication and ends with both players knowing the coloring. Combin
 ed with a folklore Ω(n) lower bound\, this settles the randomized communi
 cation complexity of (Δ+1)-coloring up to constant factors.Based on joint
  work with Maxime Flin.\n
URL:https://www.tcs.tifr.res.in/web/events/1442
DTSTART;TZID=Asia/Kolkata:20240705T143000
DTEND;TZID=Asia/Kolkata:20240705T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR