Alan Louis Selman (April 2, 1941 – January 22, 2021) was a mathematician and

theoretical computer scientist computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the th ...

known for his research on structural complexity theory, the study of computational complexity in terms of the relation between

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 spa ...

es rather than individual algorithmic problems.

Education and career

Selman was a graduate of the City College of New York. He earned a master's degree at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

before completing his Ph.D. in 1970 at Pennsylvania State University. His dissertation, ''Arithmetical Reducibilities and Sets of Formulas Valid in Finite Structures'', was supervised by Paul Axt, a student of

Stephen Cole Kleene Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...

. He became a postdoctoral researcher at Carnegie Mellon University, and an assistant professor of mathematics at Florida State University, before moving to the computer science department of

Iowa State University Iowa State University of Science and Technology (Iowa State University, Iowa State, or ISU) is a public land-grant research university in Ames, Iowa. Founded in 1858 as the Iowa Agricultural College and Model Farm, Iowa State became one of the ...

, eventually becoming a full professor there. In the late 1980s he moved to Northeastern University, becoming acting dean there, and in 1990 he moved again to the

University at Buffalo The State University of New York at Buffalo, commonly called the University at Buffalo (UB) and sometimes called SUNY Buffalo, is a public research university with campuses in Buffalo and Amherst, New York. The university was founded in 18 ...

as chair of computer science. He retired in 2014, and died on January 22, 2021. He was the first chair of the annual

Computational Complexity Conference The Computational Complexity Conference (CCC), is an academic conference in the field of theoretical computer science whose roots date to 1986. It fosters research in computational complexity theory, and is typically held annually between mid-May an ...

, and served as editor-in-chief of the journal ''

Theory of Computing Systems ''Theory of Computing Systems'' is a peer-reviewed scientific journal published by Springer Verlag. Published since 1967 as ''Mathematical Systems Theory'' and since volume 30 in 1997 under its current title, it is devoted to publishing origi ...

'' for 18 years, beginning in 2001.

Selected publications

Selman's research publications included well-cited works on the classification of different types of reductions according to their computational power, the formulation of

promise problem In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the ''yes'' instances (the inputs for whi ...

s, the complexity class UP of problems solvable by unambiguous Turing machines, and their applications to the computational complexity of

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

: * * * As well as being the editor of several

edited volume An edited volume or edited collection is a collection of scholarly or scientific chapters written by different authors. The chapters in an edited volume are original works (not republished works). Alternative terms for edited volume are ''contrib ...

s, Selman was the coauthor of the textbook ''Computability and Complexity Theory'' (with Steve Homer, Springer, 2001; 2nd ed., 2011).

Recognition

Selman was a Fulbright Scholar and Humboldt Fellow. He was named an

ACM Fellow ACM or A.C.M. may refer to: Aviation * AGM-129 ACM, 1990–2012 USAF cruise missile * Air chief marshal * Air combat manoeuvring or dogfighting * Air cycle machine * Arica Airport (Colombia) (IATA: ACM), in Arica, Amazonas, Colombia Computing * ...

in 1998, as "an influential contributor to computational complexity theory and a dedicated professional within the academic computer science community". In 2002,

ACM SIGACT ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publi ...

(the Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery) gave him their Distinguished Service Prize, noting his work in helping to found the Computational Complexity Conference and in helping to fund theoretical computer science research through his work drafting policy reports for the

National Science Foundation The National Science Foundation (NSF) is an independent agency of the United States government that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National ...

. The journal ''Theory of Computing Systems'' is organizing a commemorative issue celebrating his memory.

References

External links

* {{DEFAULTSORT:Selman, Alan 1941 births 2021 deaths 20th-century American mathematicians 21st-century American mathematicians American computer scientists Theoretical computer scientists City College of New York alumni University of California, Berkeley alumni Pennsylvania State University alumni Florida State University faculty Iowa State University faculty Fellows of the Association for Computing Machinery