The Evolving Landscape of Dynamic Complexity

24^th October 2025, 11:00 ALT
Anish Mukherjee 

Abstract

Dynamic 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.

A 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.