BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Advancements in Online Edge Coloring Algorithms
DTSTART:20251128T165000
DTEND:20251128T175000
DTSTAMP:20260427T231352Z
UID:ddeb7ad37f5f745b283973da7d420d677b3f8d50167182e0c618ec25
CATEGORIES:Conferences - Seminars
DESCRIPTION:Ola Svensson (EPFL)\nIn this presentation\, we explore recent 
 advancements in online edge coloring\, focusing on new algorithms that ach
 ieve near-optimal guarantees by leveraging martingale concentration argume
 nts. Our focus will be on two main results that establish sharp thresholds
  matching long-standing lower bounds\, answering and pushing beyond the or
 iginal conjecture by Bar-Noy\, Motwani\, and Naor (BNMN\, 1992). \n\nFirs
 tly\, while the BNMN conjecture posited that randomization was necessary t
 o achieve (1+o(1))Delta-coloring for Delta=omega(log n)\, we present a det
 erministic online algorithm that achieves this guarantee in the same regim
 e. This result matches the known impossibility result for deterministic al
 gorithms when Delta=O(log n)\, establishing a sharp threshold. \n\nSecond
 ly\, improving the conditions under which near-optimal coloring is known t
 o be possible randomly\, we present a randomized online algorithm achievin
 g a (1+o(1))Delta-edge-coloring already for graphs with maximum degree Del
 ta=omega(sqrt{log n}). This establishes a sharp threshold for randomized a
 lgorithms\, matching the BNMN lower bound for the Delta=O(sqrt{log n}) reg
 ime. \n\nThis is joint work with Joakim Blikstad\, Ola Svensson\, Radu 
 Vintan\, and David Wajc.
LOCATION:GA 3 21 https://plan.epfl.ch/?room==GA%203%2021
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR