Larry J. Stockmeyer

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

Larry Stockmeyer
Biographie
Naissance
Décès
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Membre de
Dir. de thèse
Distinctions

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 « The Complexity of Decision Problems in Automata Theory and Logic »[1].

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[2] qui introduit la hiérarchie polynomiale. Les machines de Turing alternantes ont été introduites, avec Ashok K. Chandra et Dexter Kozen[3]. 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

Publications principales (sélection)

Notes

Bibliographie

Appréciation des contributions
Notices nécrologiques

Liens externes

Article connexe

  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.