Alan Louis Selman (April 2, 1941 – January 22, 2021)[1] was a 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 classes rather than individual algorithmic problems.[2][3]
Alan L. Selman | |
|---|---|
 Alan L. Selman | |
| Born | April 2, 1941 |
| Died | January 22, 2021 (aged 79) |
| Alma mater | BS, City College of New York, 1962 MA, University of California, Berkeley, 1964 PhD, Pennsylvania State University, 1970 |
| Known for | Structural complexity theory |
| Spouse | Sharon Selman |
| Awards | ACM Fellow Fulbright Award Humboldt Research Award University at Buffalo Exceptional Scholar Award SUNY Chancellor's Award for Excellence in Scholarship and Creative Activities Japan Society for the Promotion of Science Invitation Fellowship ACM SIGACT Distinguished Service Prize IEEE Computer Society Meritorious Service Award for founding the Symposium on Structure in Complexity |
| Scientific career | |
| Fields | Theoretical computer science Mathematics |
| Thesis | Arithmetical Reducibilities and Sets of Formulas Valid in Finite Structures (1970) |
| Doctoral advisor | Paul Axt |
| Doctoral students | Joachim Grollman John Geske Roy Rubinstein Ashish Naik A. Pavan S. Sengupta Liyu Zhang Dung Nguyeen Andrew Hughes Mitsunori Ogihara (postdoctoral advisee) Edith Hemaspaandra (postdoctoral advisee) Christian Glasser (postdoctoral advisee) |
Education and career
editSelman was a graduate of the City College of New York. He earned a master's degree at the University of California, Berkeley before completing his Ph.D. in 1970 at Pennsylvania State University.[4] His dissertation, Arithmetical Reducibilities and Sets of Formulas Valid in Finite Structures, was supervised by Paul Axt, a student of Stephen Cole Kleene.[5]
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, 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 as chair of computer science. He retired in 2014, and died on January 22, 2021.[4]
He was the first chair of the annual Computational Complexity Conference,[4] and served as editor-in-chief of the journal Theory of Computing Systems for 18 years,[6] beginning in 2001.[3]
Selected publications
editSelman's research publications included well-cited works on the classification of different types of reductions according to their computational power, the formulation of promise problems, the complexity class UP of problems solvable by unambiguous Turing machines, and their applications to the computational complexity of cryptography:[2][3]
- Ladner, R. E.; Lynch, N. A.; Selman, A. L. (1975), "A comparison of polynomial time reducibilities", Theoretical Computer Science, 1 (2): 103–123, doi:10.1016/0304-3975(75)90016-X, MR 0395319
- Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), "The complexity of promise problems with applications to public-key cryptography", Information and Control, 61 (2): 159–173, doi:10.1016/S0019-9958(84)80056-X, MR 0772678
- Grollmann, Joachim; Selman, Alan L. (1988), "Complexity measures for public-key cryptosystems", SIAM Journal on Computing, 17 (2): 309–335, doi:10.1137/0217018, MR 0935342
As well as being the editor of several edited volumes, Selman was the coauthor of the textbook Computability and Complexity Theory (with Steve Homer, Springer, 2001; 2nd ed., 2011).[7]
Recognition
editSelman was a Fulbright Scholar and Humboldt Fellow.[4] 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".[8] In 2002, ACM SIGACT (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.[9]
The journal Theory of Computing Systems is organizing a commemorative issue celebrating his memory.[6]
References
edit- ^ Selman, Sharon, In memoriam, University at Buffalo, retrieved 2021-08-06
- ^ a b Fenner, Stephen (March 2021), "Remembrances of Alan", ACM SIGACT News, 52 (1): 87–93, doi:10.1145/3457588.3457603, S2CID 232245680
- ^ a b c Hemaspaandra, Lane A. (September 2014), "Beautiful structures: An appreciation of the contributions of Alan Selman", ACM SIGACT News, 45 (3): 54–70, doi:10.1145/2670418.2670436, S2CID 1948170
- ^ a b c d Dr. Alan L. Selman 1941-2021, Iowa State University Department of Computer Science, February 12, 2021, retrieved 2021-08-06
- ^ Alan Selman at the Mathematics Genealogy Project
- ^ a b "Commemorative Issue for Alan L. Selman", Journal updates: Theory of Computing Systems, Springer, retrieved 2021-08-06
- ^ Reviews of Computability and Complexity Theory:
- Anatoly V. Anisimov (1st ed.), Zbl 1033.68045
- Eowyn W. Čenek (2002, 1st ed.), ACM SIGACT News, doi:10.1145/582475.582480
- Jeffrey Shallit (2013, 2nd ed.), ACM SIGACT News, doi:10.1145/2556663.2556672
- Heribert Vollmer (2nd ed.), Zbl 1248.68192
- ^ "Alan Selman", ACM Fellows, Association for Computing Machinery, retrieved 2021-08-06
- ^ 2002 ACM-SIGACT Distinguished Service Prize: Alan Selman, ACM SIGACT, retrieved 2021-08-06
External links
edit- Alan Selman publications indexed by Google Scholar