Descriptive Complexity: Survey and Recent Progress

  • Neil Immerman | College of Information and Computer Sciences, UMass, Amherst

In Descriptive Complexity, we ask how rich a logical language is needed to describe a given computational problem. It is natural that there might sometimes be a relation between descriptive complexity and traditional computational complexity. Remarkably, there is an isomorphism. In fact, the most important complexity classes have very natural descriptive characterizations.

I will give a survey about descriptive complexity including recent progress in understanding dynamic problems – where we are computing properties of inputs that change over time. There are applications to database problems as well as to reasoning about the correctness of programs.

Speaker Details

Professor Neil Immerman is a key developer of descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory. His book, Descriptive Complexity, appeared in 1999. Immerman is the winner, jointly with Róbert Szelepcsényi, of the 1995 Gödel Prize in theoretical computer science. Immerman is an ACM Fellow and a Guggenheim Fellow.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks