2:00 pm, Seminar Hall
Lower Bounds for Descriptive Dynamic Complexity
Thomas Zeume
TU Dortmund.
20-02-15

---

Abstract

In modern data management scenarios, data is subject to frequent changes. In order to avoid costly re-computations from scratch after each small update, one can try to (re-)use auxiliary data structures that have been already computed before to keep the information about the data up-to-date. However, the auxiliary data structures need to be updated dynamically whenever the data changes.

The descriptive dynamic complexity framework (short: dynamic complexity) introduced by Patnaik and Immerman models this setting. It was mainly inspired by relational databases. For a relational database subject to change, auxiliary relations are maintained with the intention to help answering a query Q. When an update to the database, i.e. an insertion or a deletion of a tuple, occurs, every auxiliary relation is updated through a first-order query that can refer to the database as well as to the auxiliary relations.

In this talk I will introduce this framework and discuss recent lower bound results.