Michael J. Fischer

Biographie
Naissance	20 avril 1942 (82 ans); Ann Arbor
Nationalité	américaine
Formation	Université Harvard; Collège de la littérature, des sciences et des arts de l'université du Michigan (en); Harvard School of Engineering and Applied Sciences (en)
Activité	Informaticien
A travaillé pour	Université Yale
Membre de	Association for Computing Machinery (1996)
Directrice de thèse	Sheila Greibach
Site web	www.cs.yale.edu/homes/fischer
Distinctions	ACM Fellow (1996); Prix Dijkstra (2001)

Michael John Fischer est un informaticien américain, né le 20 avril 1942 à Ann Arbor (Michigan), qui travaille dans les domaines de calcul distribué, parallélisme (informatique), cryptographie, algorithmique et structures de données et en théorie de la complexité.

Carrière

Michael Fischer obtient un BSc en mathématiques à l'université du Michigan en 1963 ; il effectue ensuite ses études de MA et PhD en mathématiques appliquées à l'université Harvard; il obtient la maîtrise en 1965 et le PhD en 1968, ce dernier sous la direction de Sheila A. Greibach, avec une thèse intitulée « Grammars with Macro-like Productions »^[1]^,^[2].

Michael Fischer est ensuite professeur assistant en informatique à l'université Carnegie-Mellon en 1968-1969, professeur assistant en mathématiques au Massachusetts Institute of Technology (MIT) en 1969-1973, et professeur associé en électrotechnique au MIT en 1973-1975. Au MIT, il supervise notamment les travaux de David S. Johnson, Frances Yao et Michael Martin Hammer^[1]. En 1975, Fischer devient professeur d'informatique à l'université de Washington ; à partir de 1981, il professeur d'informatique à l'université Yale.

Fischer a été professeur ou chercheur invité à l'Université de la Sarre (automne 1988), au Georgia Institute of Technology (printemps 1980), au l'EPFZ (été 1975), à l'Université de Francfort (été 1974), Université de Toronto (printemps 1974), Université de Warwick (été 1972)^[2].

Responsabilités et distinctions

Fischer a été rédacteur-en-chef du Journal of the ACM entre 1982 et 1986^[3]^,^[4]. Il est élu Fellow de l'Association for Computing Machinery (ACM) en 1996^[5]^,^[6] « pour ses contributions techniques exceptionnelles à l'informatique théorique et pour ses services dévoués à la communauté informatique »^[7].

Fischer est membre de l'European Association for Theoretical Computer Science et de l’American Mathematical Society. Il a été membre et aussi président de nombreux comités de programmes de conférences comme Symposium on Theory of Computing, Symposium on Foundations of Computer Science, et bien sûr Symposium on Principles of Distributed Computing. Il a été conférencier invité à de nombreuses conférences également.

Travaux scientifiques

Fischer est connu pour ses contributions en algorithmique répartie. Son article de 1985 avec Nancy A. Lynch et Michael S. Paterson^[8] sur le problème de consensus a obtenu le prix Edsger W. Dijkstra en algorithmique répartie en 2001^[9].

Fischer était le président du comité de programme du premier Symposium on Principles of Distributed Computing (en) (PODC) en 1982^[10]; PODC est devenue la conférence principale dans ce domaine. En 2003, le 22^e PODC comprenait une série de communications à l'occasion du 60^e anniversaire de Fischer^[11], avec comme orateurs Leslie Lamport, Nancy Lynch, Albert R. Meyer^[12] et Rebecca Wright^[13].

En 1980, Fischer et Richard E. Ladner^[14] présentent un algorithme parallèle pour le calcul parallèle des sommes préfixes^[15]. Le même circuit avait déjà été étudié plus tôt en URSS^[16]^,^[17].

Fischer a également travaillé en analyse syntaxique et sur les grammaires formelles dès sa thèse^[12], sur le string matching^[18] et sur l'algorithme pour l'union-find^[19].

Fischer s'est intéresse très tôt au vote électronique. En 1985, Fischer et Josh Cohen Benaloh^[20] présentent un des premiers schémas de vote électronique^[13].

Il s'intéresse aussi au problème d'échange de clés et au transfert inconscient^[13]. En 1984, Fischer, Silvio Micali, et Charles Rackoff présentent un protocole, publié en 1996^[21], qui est une version améliorée du protocole de transfert inconscient de Michael O. Rabin.

Publications (sélection)

Bernard A. Galler et Michael J. Fischer, « An improved equivalence algorithm », Communications of the ACM, vol. 7, n^o 5,‎ 1964, p. 301–303 (DOI 10.1145/364099.364331)^[12].
Robert A. Wagner et Michael J. Fischer, « The string-to-string correction problem », Journal of the ACM, vol. 21, n^o 1,‎ 1974, p. 168–173 (DOI 10.1145/321796.321811).
Richard E. Ladner et Michael J. Fischer, « Parallel prefix computation », Journal of the ACM, vol. 27, n^o 4,‎ 1980, p. 831–838 (DOI 10.1145/322217.322232)^[12].
Michael J. Fischer, Nancy A. Lynch et Michael S. Paterson, « Impossibility of distributed consensus with one faulty process », Journal of the ACM, vol. 32, n^o 2,‎ 1985, p. 374–382 (DOI 10.1145/3149.214121)^[22].
Josh D. Cohen et Michael J. Fischer, « A robust and verifiable cryptographically secure election scheme », 26th Annual Symposium on Foundations of Computer Science,‎ 1985, p. 372–382 (DOI 10.1109/SFCS.1985.2)^[13].
Michael J. Fischer, Silvio Micali et Charles Rackoff, « A secure protocol for the oblivious transfer (extended abstract) », Journal of Cryptology, vol. 9, n^o 3,‎ 1996, p. 191–195 (DOI 10.1007/BF00208002)^[13].

Notes et références

↑ ^{a et b} (en) « Michael John Fischer », sur le site du Mathematics Genealogy Project.
↑ ^{a et b} Données biographiques de Michael Fischer.
↑ « Journal of the ACM (JACM), Volume 30, Issue 1 (January 1983) », ACM Portal (consulté le 6 juillet 2009)
↑ « Journal of the ACM (JACM), Volume 33, Issue 3 (July 1986) », ACM Portal (consulté le 6 juillet 2009).
↑ « ACM Fellows » [archive du 1^er janvier 2009], ACM (consulté le 6 juillet 2009)
↑ « ACM: Fellows Award / Michael J Fischer », ACM (consulté le 6 juillet 2009)
↑ « For outstanding technical contributions to theoretical computer science, and for dedicated service to the computer science community. »
↑ Fischer, Lynch et Paterson 1985.
↑ « PODC Influential Paper Award: 2001 » (consulté le 6 juillet 2009)
↑ « A chronological history of SIGOPS », ACM SIGOPS (consulté le 6 juillet 2009)
↑ « Twenty-Second ACM Symposium on Principles of Distributed Computing (PODC 2003), July 13-16, 2003, Boston, Massachusetts » (consulté le 6 juillet 2009)
↑ ^{a b c et d} Albert R. Meyer, « M. J. Fischer, et al., the first decade: mid-60's to 70's », Proceedings PODC 2003, 12 juillet 2003 (consulté le 6 juillet 2009) Slides de l'exposé 2003.
↑ ^{a b c d et e} Rebecca N. Wright, « Fischer's cryptographic protocols », Proceedings. PODC,‎ 2003, p. 20–22 (DOI 10.1145/872035.872039, lire en ligne).
↑ Ladner et Fischer 1980.
↑ Aaron Harwood, « Ladner and Fischer's parallel prefix algorithm », Networks and Parallel Processing Complexity – Notes, 2003 (consulté le 7 juillet 2009).
↑ (ru) Yu P. Offman, « On the Algorithmic Complexity of Discrete Functions », Dokl. Akad. Nauk SSSR, vol. 145, n^o 1,‎ 1962, p. 48–51 — Traduction anglaise dans Soviet Physics Doklady, vol. 7, 1963|pages 589–591.
↑ A. N. Krapchenko, « Asymptotic Estimation of Addition Time of a Parallel Adder », Syst. Theory Res., vol. 19,‎ 1970, p. 105–122.
↑ Wagner et Fischer 1974.
↑ Galler et Fischer 1964
↑ Cohen et Fischer 1985
↑ Fischer, Micali et Rackoff 1996.
↑ PODC Influential-Paper Award in 2001.

Liens externes

Page personnelle sur l'université Yale
(en) « Michael John Fischer », sur le site du Mathematics Genealogy Project
Publications de Michael J. Fischer sur DBLP
Michael J. Fischer sur zbMATH
Fischer, Michael J. sur MathSciNet
Notices d'autorité :
- VIAF
- LCCN
- WorldCat
Ressources relatives à la recherche :

Portail de l'informatique théorique

[mg-1] {a et b} (en) « Michael John Fischer », sur le site du Mathematics Genealogy Project.

[cv-2] {a et b} Données biographiques de Michael Fischer.

[3] « Journal of the ACM (JACM), Volume 30, Issue 1 (January 1983) », ACM Portal (consulté le 6 juillet 2009)

[4] « Journal of the ACM (JACM), Volume 33, Issue 3 (July 1986) », ACM Portal (consulté le 6 juillet 2009).

[5] « ACM Fellows » [archive du 1^er janvier 2009], ACM (consulté le 6 juillet 2009)

[6] « ACM: Fellows Award / Michael J Fischer », ACM (consulté le 6 juillet 2009)

[7] « For outstanding technical contributions to theoretical computer science, and for dedicated service to the computer science community. »

[8] Fischer, Lynch et Paterson 1985.

[podc-award-9] « PODC Influential Paper Award: 2001 » (consulté le 6 juillet 2009)

[10] « A chronological history of SIGOPS », ACM SIGOPS (consulté le 6 juillet 2009)

[11] « Twenty-Second ACM Symposium on Principles of Distributed Computing (PODC 2003), July 13-16, 2003, Boston, Massachusetts » (consulté le 6 juillet 2009)

[meyer03-12] {a b c et d} Albert R. Meyer, « M. J. Fischer, et al., the first decade: mid-60's to 70's », Proceedings PODC 2003, 12 juillet 2003 (consulté le 6 juillet 2009) Slides de l'exposé 2003.

[wright03-13] {a b c d et e} Rebecca N. Wright, « Fischer's cryptographic protocols », Proceedings. PODC,‎ 2003, p. 20–22 (DOI 10.1145/872035.872039, lire en ligne).

[14] Ladner et Fischer 1980.

[15] Aaron Harwood, « Ladner and Fischer's parallel prefix algorithm », Networks and Parallel Processing Complexity – Notes, 2003 (consulté le 7 juillet 2009).

[offman-16] (ru) Yu P. Offman, « On the Algorithmic Complexity of Discrete Functions », Dokl. Akad. Nauk SSSR, vol. 145, n^o 1,‎ 1962, p. 48–51 — Traduction anglaise dans Soviet Physics Doklady, vol. 7, 1963|pages 589–591.

[krapchenko-17] A. N. Krapchenko, « Asymptotic Estimation of Addition Time of a Parallel Adder », Syst. Theory Res., vol. 19,‎ 1970, p. 105–122.

[18] Wagner et Fischer 1974.

[19] Galler et Fischer 1964

[20] Cohen et Fischer 1985

[21] Fischer, Micali et Rackoff 1996.

[22] PODC Influential-Paper Award in 2001.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Naissance	20 avril 1942 (82 ans) Ann Arbor
Nationalité	américaine
Formation	Université Harvard Collège de la littérature, des sciences et des arts de l'université du Michigan (en) Harvard School of Engineering and Applied Sciences (en)
Activité	Informaticien