Descriptive Complexity

Neil Immerman is one of the key developers of 'descriptive complexity', which he is currently applying to research in model checking, database theory, and computational complexity theory. 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. His book, 'Descriptive Complexity', appeared in 1999.

Abstract: Descriptive complexity measures the richness of logical languages that are needed to describe computational tasks. Fagin proved that the complexity class NP is exactly the set of problems expressible in second-order existential logic. Since that time, all natural complexity classes have been characterized by natural descriptive measures. This approach has helped solve some basic problems in complexity theory as well as offering insights into related areas.

I will survey a few of the high points of descriptive complexity and talk about some current directions including applications to dynamic algorithms, static analysis of programs, and progress in understanding the trade-off between parallel time and amount of computational hardware. This will be a general interest talk -- not just for theoreticians and logicians.