Larry J. Stockmeyer

Larry Stockmeyer

Biographie
Naissance	1948
Décès	31 juillet 2004
Nationalité	américaine
Formation	Massachusetts Institute of Technology
Activités	Informaticien, ingénieur

Autres informations
A travaillé pour	Université de Californie à Santa Cruz
Membre de	Association for Computing Machinery (1996)
Directeur de thèse	Albert R. Meyer
Distinctions	ACM Fellow (1996) Prix Dijkstra (2007)

modifier - modifier le code - modifier Wikidata

Larry Joseph Stockmeyer (né en 1948 à Evansville, en Indiana, et mort le 31 juillet 2004) 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 « 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 à novembre 2003 à IBM Research, Almaden Research Center, San Jose, CA. Enfin à partir d'octobre 2002 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

1996: Fellow de l'Association for Computing Machinery: « For several fundamental contributions to computational complexity theory, which have significantly affected the course of this field. »^[4]
2007: Prix Dijkstra pour l’article Dwork, Lynch et Stockmeyer 1988^[5]^,^[6].

Publications principales (sélection)

Albert R. Meyer et Larry J. Stockmeyer, « The equivalence problem for regular expressions with squaring requires exponential space », Proc. 13th Annual Symposium on Switching and Automata Theory,‎ 1972, p. 125–129 (DOI 10.1109/SWAT.1972.29). — Cet article introduit la hiérarchie polynomiale^[7]^,^[8].
Larry J. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic, 1974 (hdl 1721.1/15540, lire en ligne). Sa thèse de Ph. D. — « one of the most remarkable doctoral theses in computer science »^[9].
Cynthia Dwork, Nancy Lynch et Larry Stockmeyer, « Consensus in the presence of partial synchrony », Journal of the ACM, vol. 35, n^o 2,‎ 1988, p. 288–323 (DOI 10.1145/42282.42283). — Cet article obtient le Prix Dijkstra in 2007^[5].
(en) Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, n^o 1,‎ 1981, p. 114–133 (ISSN 0004-5411, DOI 10.1145/322234.322243)

Notes

↑ Stockmeyer 1974.
↑ Meyer et Stockmeyer 1972.
↑ Chandra, Kozen et Stockmeyer 1981.
↑ ACM: Fellows Award / Larry Stockmeyer.
↑ ^{a et b} Dijkstra Prize 2007 sur Symposium on Principles of Distributed Computing (en)
↑ Bortnikov 2007.
↑ Fortnow 2005.
↑ Rajsbaum 2004.
↑ STOC 2005 program.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Larry J. Stockmeyer » (voir la liste des auteurs).

Bibliographie

Appréciation des contributions

Edward Bortnikov, « Review of DISC '07 », ACM SIGACT News, vol. 38, n^o 4,‎ 2007, p. 49–53 (ISSN 0163-5700, DOI 10.1145/1345189.1386170).
Lance Fortnow, « Beyond NP: the work and legacy of Larry Stockmeyer », Proc. 37th Annual ACM Symposium on Theory of Computing (STOC, Baltimore, MD, USA, 2005),‎ 2005, p. 120–127 (ISBN 1-58113-960-8, DOI 10.1145/1060590.1060609, lire en ligne).

Notices nécrologiques

Sergio Rajsbaum, « Larry Stockmeyer: 1948–2004 », ACM SIGACT News, vol. 35, n^o 4,‎ 2004, p. 39 (ISSN 0163-5700, DOI 10.1145/1054916.1054930).
« In Memoriam – Larry Stockmeyer », UC Santa Cruz Currents Online, 9 août 2004
« STOC 2005 conference program » Includes the program of 'Larry Stockmeyer Commemoration' (21 May 2005).