Corelab Seminar

Ioannis Kokkinis
An Introduction to Dynamic Complexity

The goal of dynamic complexity is to determine the minimum resources needed for maintaining the answer to a problem (query) when the input (database) changes dynamically. An important dynamic complexity class is the class DynFO which contains all queries that can be maintained using first order formulas after single tuple insertions and deletions into/from the database. The class DynFO was introduced in 1997 by Patnaik and Immerman as a small parallel descriptive complexity class that would help us classify some dynamic database problems. Although the updates to the problems belonging in DynFO are only possible in first-order logic, DynFO has proven to be quite powerful: it even contains the reachability query, which is a natural NL-complete problem. However several natural questions for this class remain open, such as an exact comparison of DynFO with classical (static) complexity classes and finding natural complete problems for DynFO.
In this talk I will give an introduction to the fundamentals of Dynamic Complexity and also a slight overview on some recent joint work with the members of the group LOGIDAC in TU Dortmund: namely combining dynamic complexity with parametrised complexity and also studying the dynamic complexity of Acyclic Conjunctive Queries.