Michael J. Fischer

Michael John Fischer (born 1942) is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity.

Career

Fischer was born in 1942 in Ann Arbor, Michigan, USA. He received his BSc degree in mathematics from the University of Michigan in 1963. Fischer did his MA and PhD studies in applied mathematics at Harvard University; he received his MA degree in 1965 and PhD in 1968. Fischer's PhD supervisor at Harvard was Sheila Greibach.

After receiving his PhD, Fischer was an assistant professor of computer science at Carnegie-Mellon University in 1968–1969, an assistant professor of mathematics at Massachusetts Institute of Technology (MIT) in 1969–1973, and an associate professor of electrical engineering at MIT in 1973–1975. At MIT he supervised doctoral students who became prominent computer scientists, including David S. Johnson, Frances Yao, and Michael Hammer.

In 1975, Fischer was nominated as a professor of computer science at the University of Washington. Since 1981, he has been a professor of computer science at Yale University. Fischer served as the editor-in-chief of the Journal of the ACM in 1982–1986.^[1][2] He was inducted as a Fellow of the Association for Computing Machinery (ACM) in 1996.^[3]

Work

Distributed computing

Fischer is famous for his contributions in the field of distributed computing. His 1985 work with Nancy A. Lynch and Michael S. Paterson^[4] on consensus problems received the PODC Influential-Paper Award in 2001.^[5] Their work showed that in an asynchronous distributed system, consensus is impossible if there is one processor that crashes. Jennifer Welch writes that “This result has had a monumental impact in distributed computing, both theory and practice. Systems designers were motivated to clarify their claims concerning under what circumstances the systems work.”^[5]

Fischer was the program chairman of the first Symposium on Principles of Distributed Computing (PODC) in 1982;^[6] nowadays, PODC is the leading conference in the field. In 2003, the distributed computing community honoured Fischer's 60th birthday by organising a lecture series during the 22nd PODC,^[7] with Leslie Lamport, Nancy Lynch, Albert R. Meyer, and Rebecca Wright as speakers.

Parallel computing

In 1980, Fischer and Richard Ladner^[8] presented a parallel algorithm for computing prefix sums efficiently. They show how to construct a circuit that computes the prefix sums; in the circuit, each node performs an addition of two numbers. With their construction, one can choose a trade-off between the circuit depth and the number of nodes.^[9] However, the same circuit designs were already studied much earlier in Soviet mathematics.^[10][11]

Algorithms and computational complexity

Fischer has done multifaceted work in theoretical computer science in general. Fischer's early work, including his PhD thesis, focused on parsing and formal grammars.^[12] One of Fischer's most-cited works deals with string matching.^[13] Already during his years at Michigan, Fischer studied disjoint-set data structures together with Bernard Galler.^[14]

Cryptography

Fischer is one of the pioneers in electronic voting. In 1985, Fischer and his student Josh Cohen Benaloh^[15] presented one of the first electronic voting schemes.^[16]

Other contributions related to cryptography include the study of key exchange problems and a protocol for oblivious transfer.^[16] In 1984, Fischer, Silvio Micali, and Charles Rackoff^[17] presented an improved version of Michael O. Rabin's protocol for oblivious transfer.

Publications

• Galler, Bernard A.; Fischer, Michael J. (1964). "An improved equivalence algorithm". Communications of the ACM 7 (5): 301–303. doi:10.1145/364099.364331 .^[12]
• Wagner, Robert A.; Fischer, Michael J. (1974). "The string-to-string correction problem". Journal of the ACM 21 (1): 168–173. doi:10.1145/321796.321811 .^[18]
• Ladner, Richard E.; Fischer, Michael J. (1980). "Parallel prefix computation". Journal of the ACM 27 (4): 831–838. doi:10.1145/322217.322232 .^[12][19]
• Fischer, Michael J.; Lynch, Nancy A.; Paterson, Michael S. (1985). "Impossibility of distributed consensus with one faulty process". Journal of the ACM 32 (2): 374–382. doi:10.1145/3149.214121 .^[20][21]
• Cohen, Josh D.; Fischer, Michael J. (1985). "A robust and verifiable cryptographically secure election scheme". Proc. Symposium on Foundations of Computer Science (FOCS). pp. 372–382. doi:10.1109/SFCS.1985.2 .^[16]
• Fischer, M. J.; Micali, S.; Rackoff, C. (1996). "A secure protocol for the oblivious transfer (extended abstract)". Journal of Cryptology 9 (3): 191–195. doi:10.1007/BF00208002 .^[16]

Notes

1. ^ "Journal of the ACM (JACM), Volume 30, Issue 1 (January 1983)". ACM Portal. http://portal.acm.org/citation.cfm?id=322358. Retrieved 2009-07-06. 
2. ^ "Journal of the ACM (JACM), Volume 33, Issue 3 (July 1986)". ACM Portal. http://portal.acm.org/citation.cfm?id=5925. Retrieved 2009-07-06. 
3. ^ "ACM Fellows". ACM. http://fellows.acm.org/homepage.cfm?alpha=M&srt=alpha. Retrieved 2009-07-06.  "ACM: Fellows Award / Michael J Fischer". ACM. http://fellows.acm.org/fellow_citation.cfm?id=1027952&srt=alpha. Retrieved 2009-07-06.  "For outstanding technical contributions to theoretical computer science, and for dedicated service to the computer science community."
4. ^ Fischer, Lynch & Paterson (1985)
5. ^ ^{a b} "PODC Influential Paper Award: 2001". http://www.podc.org/influential/2001.html. Retrieved 2009-07-06. 
6. ^ "A chronological history of SIGOPS". ACM SIGOPS. http://www.sigops.org/history.html. Retrieved 2009-07-06. 
7. ^ "Twenty-Second ACM Symposium on Principles of Distributed Computing (PODC 2003), July 13-16, 2003, Boston, Massachusetts". http://www.podc.org/podc2003/. Retrieved 2009-07-06. 
8. ^ Ladner & Fischer (1980).
9. ^ Harwood, Aaron (2003). "Ladner and Fischer's parallel prefix algorithm". Networks and Parallel Processing Complexity – Notes. http://www.cs.mu.oz.au/498/notes/node25.html. Retrieved 2009-07-07. .
10. ^ Offman, Y. P. (1962). "On the Algorithmic Complexity of Discrete Functions" (in Russian). Dokl. Sov. Acad. Sci. 145 (1): 48–51 . English translation in Sov. Phys. Dokl. 7 (7): 589–591 1963.
11. ^ Krapchenko, A. N. (1970). "Asymptotic Estimation of Addition Time of a Parallel Adder". Syst. Theory Res. 19: 105–122 .
12. ^ ^{a b c} Meyer, Albert R. (12 July 2003). "M.J. Fischer, et al., the first decade: mid-60's to 70's". http://people.csail.mit.edu/meyer/fischer-fest.pdf. Retrieved 2009-07-06.  Slides from PODC 2003.
13. ^ Wagner & Fischer (1974).
14. ^ Galler & Fischer (1964)
15. ^ Cohen & Fischer (1985)
16. ^ ^{a b c d} Wright, Rebecca N. (2003). "Fischer's cryptographic protocols". Proc. PODC 2003. pp. 20–22. doi:10.1145/872035.872039 .
17. ^ Fischer, Micali & Rackoff (1996), originally presented in 1984.
18. ^ "1592 citations". Google Scholar. http://scholar.google.com/scholar?cites=1168026360880314540. Retrieved 2009-07-06. 
19. ^ "726 citations". Google Scholar. http://scholar.google.com/scholar?cites=17348117272132242802. Retrieved 2009-07-07. 
20. ^ PODC Influential-Paper Award in 2001.
21. ^ "2431 citations". Google Scholar. http://scholar.google.com/scholar?cites=11993555002424078114. Retrieved 2009-07-06. 

References

• "Home page of Michael J. Fischer". http://www.cs.yale.edu/homes/fischer/. Retrieved 2009-07-06. 
• "Michael J. Fischer, Professor of Computer Science". Yale University, Computer Science. http://www.cs.yale.edu/people/fischer.html. Retrieved 2009-07-06. 
• "Michael John Fischer". Mathematics Genealogy Project. http://genealogy.math.ndsu.nodak.edu/id.php?id=40759. Retrieved 2009-07-06. 
• "Michael J. Fischer". DBLP. http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/f/Fischer:Michael_J=.html. Retrieved 2009-07-06.  List of publications.
• "Fischer, Michael J.". MathSciNet. http://www.ams.org/mathscinet/search/author.html?mrauthid=67165. Retrieved 2009-07-06. 

Persondata
Name	Fischer, Michael J.
Alternative names
Short description
Date of birth	1942
Place of birth
Date of death
Place of death