Neil Immerman (born 24 November 1953,

Manhasset, New York Manhasset is an affluent Hamlet (New York), hamlet and census-designated place (CDP) in Nassau County, New York, Nassau County, on the North Shore (Long Island), North Shore of Long Island, in New York (state), New York, United States. It is co ...

) is an American theoretical computer scientist, a professor of computer science at the

University of Massachusetts Amherst The University of Massachusetts Amherst (UMass Amherst) is a public land-grant research university in Amherst, Massachusetts, United States. It is the flagship campus of the University of Massachusetts system and was founded in 1863 as the ...

.Faculty directory: Neil Immerman
Computer Science Department,

, retrieved 2010-01-23. He is one of the key developers of

descriptive complexity Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the formal language, languages in them. For example, PH (complexity), PH, ...

, an approach he is currently applying to research in model checking, database theory, and computational complexity theory. Professor Immerman is an editor of the ''

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation i ...

'' and of ''

Logical Methods in Computer Science ''Logical Methods in Computer Science'' (LMCS) is a peer-reviewed open access scientific journal covering theoretical computer science and applied logic. It opened to submissions on September 1, 2004. The editor-in-chief is Stefan Milius ( Friedric ...

''. He received B.S. and M.S. degrees from

Yale University Yale University is a Private university, private Ivy League research university in New Haven, Connecticut, United States. Founded in 1701, Yale is the List of Colonial Colleges, third-oldest institution of higher education in the United Stat ...

in 1974 and his Ph.D. from

Cornell University Cornell University is a Private university, private Ivy League research university based in Ithaca, New York, United States. The university was co-founded by American philanthropist Ezra Cornell and historian and educator Andrew Dickson W ...

in 1980 under the supervision of

Juris Hartmanis Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established ...

, a

Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...

winner at Cornell. His book ''

Descriptive Complexity Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the formal language, languages in them. For example, PH (complexity), PH, ...

'' appeared in 1999. Immerman is the winner, jointly with Róbert Szelepcsényi, of the 1995

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

in theoretical computer science for proof of what is known as the

Immerman–Szelepcsényi theorem In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for wh ...

, the result that

nondeterministic space In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE. Complexity classes The me ...

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

es are closed under complementation. Immerman is an

ACM Fellow ACM Fellowship is an award and fellowship that recognises outstanding members of the Association for Computing Machinery (ACM). The title of ACM Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals ...

and a

Guggenheim Fellow Guggenheim Fellowships are grants that have been awarded annually since by the John Simon Guggenheim Memorial Foundation, endowed by the late Simon and Olga Hirsh Guggenheim. These awards are bestowed upon individuals who have demonstrated d ...

.Neil Immerman
, John Simon Guggenheim Memorial Foundation, retrieved 2010-01-23.

References

External links

Immerman's home page
at U. Mass. Amherst Cornell University alumni 2002 fellows of the Association for Computing Machinery Gödel Prize laureates University of Massachusetts Amherst faculty Living people American theoretical computer scientists People from Manhasset, New York Scientists from New York (state) 1953 births {{compu-bio-stub