Pacific Institute for the Mathematical Sciences - PIMS

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.

PIMS/SFU Computing Science DISTINGUISHED LECTURE SERIES 2007