Recent Progress in Dynamic Complexity Theory

In dynamic complexity, one is typically interested in the parallel resources needed for maintaining a query after a small change to the input. While, in the classical setting of static inputs, parallel constant-time algorithms are well-studied (e.g., in CRCW-PRAMs or AC^0 circuits) -- our understanding in the dynamic setting is rather limited. 

Whether reachability can be maintained by dynamic AC^0 circuits, was one of the major open questions since the inception of the field, which we confirmed recently, after two decades. Since then, significant progress has been made in this area, primarily on the algorithmic front. Interestingly, many such algorithms are based on some algebraic or counting techniques. In this talk, I will discuss some of these recent results and mention various future directions.