Neil Immerman

Neil Immerman is one of the key developers of an active research program called descriptive complexity. This area applies logic to computational complexity, discerning strong mathematical structure underlying standard complexity measures. In a striking series of results, Immerman has shown how all important complexity measures have natural descriptive characterizations. Using this characterization of complexity classes, Immerman showed the very surprising result that non-deterministic space is closed under complement. The negation of this result was a common, well-believed conjecture that had stood open for 25 years. Robert Szelepcsenyi proved this result independently.

The same tools of descriptive complexity have wide applicability in database theory. For example, Immerman showed that DATALOG expresses exactly the polynomial-time queries. With his students, Immerman has studied "dynamic complexity," the complexity of queries measured by changes to the database, rather than by the size of the database itself. The dynamic complexity class dynFO captures the set of dynamic queries computable by a first-order query language; this corresponds to SQL without aggregation (the ability to count).

In addition, the logical tools that Immerman has developed have deep applicability in static analysis. In a long and continuing series of papers with Tom Reps, Mooly Sagiv, and related students and colleagues, Immerman studies when and how one can reason about reachability, e.g., when one portion of memory is reachable from another via a series of pointers. These methods are used to automatically check the correctness of programs that manipulate data. This aspect of Immerman's research has valuable applications to software including software-defined networks.

Professor Immerman is the winner, jointly with Robert Szelepcsenyi, of the 1995 Godel Prize in theoretical computer science. He has chaired several program committees (International Workshop on Logic and Computational Complexity, Finite Model Theory Workshop, and Structure in Complexity Theory Workshop); served on many program committees, including LICS, PODS, STOC, and Structures; and served on a number of editorial boards (SIAM Journal of Computing, Chicago Journal of Theoretical Computer Science, Information and Computation, and Journal of Symbolic Logic). He currently serves as an associate editor on Logical Methods in Computer Science and edits the "Logic and Complexity" column for the ACM SigLog newsletter. He is also an ACM Fellow and a Guggenheim Fellow.