BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T121148Z
UID:Seminar-pizza-1341@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Qiyi Tang:MAILTO:Qiyi.Tang@liverpool.ac.uk
DTSTART:20251216T120000
DTEND:20251216T130000
SUMMARY:Friday Lunch and Talk Series
DESCRIPTION:Will Rosenbaum: Locally Checkable Problems: Distance, Volume, and Beyond\n\nLocally Checkable Labeling Problems (LCLs) are problems defined on bounded degree graphs in which a valid solution can be verified by examining a constant radius neighborhood around each vertex in the graph. Familiar examples include computing maximal independent sets, maximal matchings, and proper colorings. While many of these problems admit simple efficient algorithms in the centralized setting, their complexities in distributed models of computation have been the subject of extensive study.\n\n\n\nIn this talk, I will give an overview of the landscape of complexities of LCLs in two distributed models of computation: the classical LOCAL model and the more recent VOLUME model. I will then discuss progress, challenges, and approaches to generalizing the results for LCLs beyond bounded degree graphs.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1341
LOCATION:ALT
END:VEVENT
END:VCALENDAR