Larry Joseph Stockmeyer (né en 1948 à Evansville, en Indiana, et mort le ) est un informaticien théoricien américain. Il est l’un des pionniers dans le domaine de la théorie de la complexité, et il a aussi apporté des contributions importantes dans le calcul distribué.
Carrière
Larry Stockmeyer obtient en 1972 un B. Sc. en mathématique au Massachusetts Institute of Technology et la même année un M. Sc. en génie électrique, toujours au Massachusetts Institute of Technology également. En 1974, il obtient un Ph. D. en informatique au Massachusetts Institute of Technology, sous la supervision d'Albert R. Meyer, avec une thèse intitulée ..
De 1974 à 1982, Stockmeyer travaille à IBM Research, au Thomas J. Watson Research Center, Yorktown Heights, NY, puis de 1982 à à IBM Research, Almaden Research Center, San Jose, CA. Enfin à partir d' et jusqu'en 2004, il est chercheur associé au Computer Science Department de l'Université de Californie à Santa Cruz.
Contributions Larry Stockmeyer a contribué à la théorie de la complexité en informatique dès son émergence, au début des années 1970, notamment sur des problèmes NP-complets. C'est l'article The equivalence problem for regular expressions with squaring requires exponential space avec Albert R. Meyer. qui introduit la hiérarchie polynomiale. Les machines de Turing alternantes ont été introduites, avec Ashok K. Chandra et Dexter Kozen.. Des applications se retrouvent dans les automates finis inambigus et d'autres problèmes de complexité. Avec Michael Garey et David S. Johnson il considère la complexité des graphes hamiltoniens. Avec Moni Naor, il travaille en théorie de Ramsey ; avec Cynthia Dwork et Nancy Lynch il obtient le prix Dijkstra en 2007.
Prix et distinctions 1996 : Fellow de l'Association for Computing Machinery: ACM: Fellows Award / Larry Stockmeyer. 2007 : Prix Dijkstra pour l’article Dijkstra Prize 2007 sur .. 2025 : Prix Dijkstra avec Moni Naor.
Publications principales (sélection)
. — Cet article introduit la hiérarchie polynomiale... . Sa thèse de Ph. D. — STOC 2005 program.. . — Cet article obtient le Prix Dijkstra in 2007.
Notes
Bibliographie Appréciation des contributions . . Notices nécrologiques .
Includes the program of 'Larry Stockmeyer Commemoration' (21 May 2005).
Liens externes Publications de Larry J. Stockmeyer sur DBLP
Article connexe Liste des Fellows de l'Association for Computing Machinery Prix Dijkstra
Catégorie:Naissance en 1948 Catégorie:Décès en juillet 2004 Catégorie:Personnalité américaine de l'informatique Catégorie:Personnalité en informatique théorique
Catégorie:Étudiant du Massachusetts Institute of Technology Catégorie:Professeur à l'université de Californie à Santa Cruz Catégorie:Lauréat du prix Dijkstra