Neil Immerman

Interests

Logic in Computer Science, computer-aided verification, complexity theory, database theory.

Research

Professor 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, Professor Immerman has shown how all important complexity measures have natural descriptive characterizations. Using this characterization of complexity classes, Professor 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 twenty-five years. Robert Szelepcsenyi proved this result independently.

The same tools of descriptive complexity have wide applicability in database theory. For example, Professor Immerman showed that DATALOG expresses exactly the polynomial-time queries. With his students, Professor 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 Professor 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, Professor 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 Professor Immerman's research has valuable applications to software including software-defined networks.

Biography

Ph.D., Cornell University (1980), M.S., Yale University (1974), B.S., Yale University (1974). Professor Immerman has been on the faculty of the University of Massachusetts Amherst since 1989, and is currently a Professor of Computer Science. He was a Visiting Professor at Stanford University (Spring 2014 and Spring 2010), University of Wisconsin-Madison (2003-2004), Cornell University (1995-1996), and Visitor, Mathematical Sciences Research Institute, Berkeley, CA (Fall 1985). A Workshop in Honor of Neil Immerman's 60th Birthday was held during the Fifteenth International Workshop on Logic and Computational Complexity in July 2014 in Vienna, Austria.

Activities & Awards

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.