September 19, 2017 Theory Seminar 4:00 pm, CS 140

Some Problems in Dynamic Descriptive Complexity Theory

Sam McGuire

Abstract: Computational complexity theory seeks to characterize the resources required to decide whether a fixed object has a particular property. In contexts where the object is not fixed, we might instead be interested in determining the resources required to maintain the answer to whether the object has such a property.

We consider such a dynamic context from a descriptive point of view. Towards this end, we define the notion of dynamic queries and discuss a framework for studying them. We’ll show upper bounds and lower bounds for the dynamic maintenance of regular languages and, time permitting, discuss the problem of dynamically counting satisfying assignments to first-order sentences.