Alan Selman
Alan L. Selman | |
---|---|
Född |
|
2 april 1941
dog | 22 januari 2021 |
(79 år)
Alma mater |
BS, City College of New York , 1962 MA, University of California, Berkeley , 1964 PhD, Pennsylvania State University , 1970 |
Känd för | Strukturell komplexitetsteori |
Make | Sharon Selman |
Utmärkelser |
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 för grundandet av Symposium on Structure i Komplexitet |
Vetenskaplig karriär | |
Fält |
Teoretisk datavetenskap Matematik |
Avhandling | Aritmetiska reducerbarheter och uppsättningar av formler giltiga i ändliga strukturer ( 1970) |
Doktorand rådgivare | Paul Axt |
Doktorander |
Joachim Grollman John Geske Roy Rubinstein Ashish Naik A. Pavan S. Sengupta Liyu Zhang Dung Nguyeen Andrew Hughes Mitsunori Ogihara (postdoktor) Edith Hemaspaandra (postdoktor) Christian Glasser (postdoktor) |
Alan Louis Selman (2 april 1941 – 22 januari 2021) var en matematiker och teoretisk datavetare känd för sin forskning om strukturell komplexitetsteori , studiet av beräkningskomplexitet i termer av förhållandet mellan komplexitetsklasser snarare än individuella algoritmiska problem.
Utbildning och karriär
Selman tog examen från City College i New York . Han tog en magisterexamen vid University of California, Berkeley innan han avslutade sin doktorsexamen. 1970 vid Pennsylvania State University . Hans avhandling, Arithmetical Reducibilities and Sets of Formulas Valid in Finite Structures , övervakades av Paul Axt, en elev till Stephen Cole Kleene .
Han blev postdoktor vid Carnegie Mellon University och biträdande professor i matematik vid Florida State University , innan han flyttade till datavetenskapsavdelningen vid Iowa State University , och så småningom blev han professor där. I slutet av 1980-talet flyttade han till Northeastern University , blev tillförordnad dekan där, och 1990 flyttade han igen till universitetet i Buffalo som ordförande för datavetenskap. Han gick i pension 2014 och dog den 22 januari 2021.
Han var den första ordföranden för den årliga Computational Complexity Conference och fungerade som chefredaktör för tidskriften Theory of Computing Systems i 18 år, med början 2001.
Utvalda publikationer
Selmans forskningspublikationer inkluderade välciterade verk om klassificeringen av olika typer av reduktioner enligt deras beräkningskraft, formuleringen av löftesproblem , komplexitetsklassen UP för problem som kan lösas av entydiga Turing-maskiner , och deras tillämpningar på kryptografins beräkningskomplexitet :
- Ladner, RE ; Lynch, NA ; Selman, AL (1975), "A comparison of polynomial time reducibilities", Theoretical Computer Science , 1 (2): 103–123, doi : 10.1016/0304-3975(75)90016-X , MR 0395319
- Till och med, 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 measurements for public-key cryptosystems", SIAM Journal on Computing , 17 (2): 309–335, doi : 10.1137/0217018 , MR 0935342
Förutom att vara redaktör för flera redigerade volymer var Selman medförfattare till läroboken Computability and Complexity Theory (med Steve Homer, Springer, 2001; 2:a upplagan, 2011).
Erkännande
Selman var en Fulbright Scholar och Humboldt Fellow. Han utsågs till ACM Fellow 1998, som "en inflytelserik bidragsgivare till beräkningskomplexitetsteori och en hängiven professionell inom den akademiska datavetenskapsgemenskapen". År 2002 ACM SIGACT (Special Interest Group on Algorithms and Computation Theory of Association for Computing Machinery ) honom deras Distinguished Service Prize, och noterade hans arbete med att hjälpa till att grunda Computational Complexity Conference och hjälpa till att finansiera teoretisk datavetenskaplig forskning genom hans arbete med att utarbeta policyrapporter för National Science Foundation .
Tidskriften Theory of Computing Systems organiserar ett jubileumsnummer för att fira hans minne.
externa länkar
- Alan Selmans publikationer indexerade av Google Scholar
- 1941 födslar
- 2021 dödsfall
- Amerikanska matematiker från 1900-talet
- Amerikanska matematiker från 2000-talet
- amerikanska datavetare
- Alumner från City College of New York
- Fellows of Association for Computing Machinery
- Florida State University-fakulteten
- Iowa State University-fakulteten
- Pennsylvania State University alumner
- Teoretiska datavetare
- University of California, Berkeley alumner