Alan Louis Selman (April 2, 1941 – January 22, 2021) was an American mathematician and theoretical computer scientist 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 s ...

es rather than individual algorithmic problems.

Education and career

Selman was a graduate of the

City College of New York The City College of the City University of New York (also known as the City College of New York, or simply City College or CCNY) is a Public university, public research university within the City University of New York (CUNY) system in 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 university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

before completing his Ph.D. in 1970 at

Pennsylvania State University The Pennsylvania State University (Penn State or PSU) is a Public university, public Commonwealth System of Higher Education, state-related Land-grant university, land-grant research university with campuses and facilities throughout Pennsyl ...

. 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 Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...

, and an assistant professor of mathematics at

Florida State University Florida State University (FSU or Florida State) is a Public university, public research university in Tallahassee, Florida, United States. It is a senior member of the State University System of Florida and a preeminent university in the s ...

, 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 university, public land-grant university, land-grant research university in Ames, Iowa, United States. Founded in 1858 as the Iowa Agricult ...

, eventually becoming a full professor there. In the late 1980s he moved to

Northeastern University Northeastern University (NU or NEU) is a private university, private research university with its main campus in Boston, Massachusetts, United States. It was founded by the Boston Young Men's Christian Association in 1898 as an all-male instit ...

, becoming acting dean there, and in 1990 he moved again to the

University at Buffalo The State University of New York at Buffalo (commonly referred to as UB, University at Buffalo, and sometimes SUNY Buffalo) is a public university, public research university in Buffalo, New York, Buffalo and Amherst, New York, United States. ...

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, and served as editor-in-chief of the journal '' Theory of Computing Systems'' 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 "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

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

edited volume Editing is the process of selecting and preparing written language, written, Image editing, visual, Audio engineer, audible, or Film editing, cinematic material used by a person or an entity to convey a message or information. The editing p ...

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 in 1998, as "an influential contributor to computational complexity theory and a dedicated professional within the academic computer science community". In 2002, ACM SIGACT (the Special Interest Group on Algorithms and Computation Theory of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...

) 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 U.S. National Science Foundation (NSF) is an Independent agencies of the United States government#Examples of independent agencies, independent agency of the Federal government of the United States, United States federal government that su ...

. 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 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 1998 fellows of the Association for Computing Machinery