BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T090212Z
UID:Seminar-pizza-1344@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Qiyi Tang:MAILTO:Qiyi.Tang@liverpool.ac.uk
DTSTART:20251024T110000
DTEND:20251024T120000
SUMMARY:Friday Lunch and Talk Series
DESCRIPTION:Anish Mukherjee : The Evolving Landscape of Dynamic Complexity\n\nDynamic complexity theory studies how queries can be maintained under small input changes using highly restricted computational models, such as AC0 circuits or first-order logic. While parallel constant-time algorithms are well understood in the static setting, our understanding in the dynamic setting, exemplified by the class DynFO, remains far less complete.\n\n\n\nA central open problem since the inception of the field was whether graph reachability can be maintained in DynFO, which was finally resolved in 2015 after two decades of effort. Over the past ten years, this breakthrough has sparked substantial progress, especially on the algorithmic side, where algebraic techniques have played a key role. In this talk, I will survey some of these developments and discuss the current boundaries of efficient dynamic computation.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1344
LOCATION:ALT
END:VEVENT
END:VCALENDAR