Neil Immerman

Neil Immerman (born 1953) is an American theoretical computer scientist and professor emeritus of computer science at the University of Massachusetts Amherst. He is one of the key developers of descriptive complexity, the approach that characterises computational complexity classes by the logical languages needed to express their problems, and he has applied it to model checking, database theory and complexity theory. He took bachelor's and master's degrees at Yale University in 1974 and a doctorate at Cornell University in 1980 under Juris Hartmanis. With Robert Szelepcsenyi he proved, independently, that nondeterministic space complexity classes are closed under complementation, the Immerman-Szelepcsenyi theorem, which earned them the 1995 Godel Prize. His book Descriptive Complexity appeared in 1999. He is an editor of the SIAM Journal on Computing and of Logical Methods in Computer Science, and is an ACM Fellow and a Guggenheim Fellow.