fbpx
Wikipedia

Michael J. Fischer

October 17, 2023

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

Career Edit

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, where his students included Rebecca N. Wright. 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 Edit

Distributed computing Edit

Fischer's 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 Edit

In 1980, Fischer and Richard E. 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 by Soviet mathematicians.[10][11]

Algorithms and computational complexity Edit

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 Edit

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 Edit

  • Galler, Bernard A.; Fischer, Michael J. (1964). "An improved equivalence algorithm". Communications of the ACM. 7 (5): 301–303. doi:10.1145/364099.364331. S2CID 9034016..[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. S2CID 13381535..[18]
  • Ladner, Richard E.; Fischer, Michael J. (1980). "Parallel prefix computation". Journal of the ACM. 27 (4): 831–838. doi:10.1145/322217.322232. S2CID 207568668..[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. S2CID 207660233..[20][21]
  • Cohen, Josh D.; Fischer, Michael J. (1985). "26th Annual Symposium on Foundations of Computer Science (SFCS 1985)". 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). pp. 372–382. doi:10.1109/SFCS.1985.2. ISBN 0-8186-0644-4..[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. S2CID 6333850..[16]

Notes Edit

  1. ^ "Journal of the ACM (JACM), Volume 30, Issue 1 (January 1983)". ACM Portal. Retrieved 2009-07-06.
  2. ^ "Journal of the ACM (JACM), Volume 33, Issue 3 (July 1986)". ACM Portal. Retrieved 2009-07-06.
  3. ^ . ACM. Archived from the original on 2009-01-01. Retrieved 2009-07-06. "ACM: Fellows Award / Michael J Fischer". ACM. 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". Retrieved 2009-07-06.
  6. ^ "A chronological history of SIGOPS". ACM SIGOPS. Retrieved 2009-07-06.
  7. ^ "Twenty-Second ACM Symposium on Principles of Distributed Computing (PODC 2003), July 13-16, 2003, Boston, Massachusetts". Retrieved 2009-07-06.
  8. ^ Ladner & Fischer (1980).
  9. ^ Harwood, Aaron (2003). . Networks and Parallel Processing Complexity – Notes. Archived from the original on 2016-03-04. Retrieved 2009-07-07..
  10. ^ Offman, Y. P. (1962). "On the Algorithmic Complexity of Discrete Functions". Dokl. Sov. Acad. Sci. (in Russian). 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" (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. Retrieved 2009-07-06.
  19. ^ "726 citations". Google Scholar. Retrieved 2009-07-07.
  20. ^ PODC Influential-Paper Award in 2001.
  21. ^ "2431 citations". Google Scholar. Retrieved 2009-07-06.

External links Edit

October 17, 2023
michael, fischer, michael, john, fischer, born, 1942, american, computer, scientist, works, fields, distributed, computing, parallel, computing, cryptography, algorithms, data, structures, computational, complexity, contents, career, work, distributed, computi. Michael John Fischer born 1942 is an American computer scientist who works in the fields of distributed computing parallel computing cryptography algorithms and data structures and computational complexity Contents 1 Career 2 Work 2 1 Distributed computing 2 2 Parallel computing 2 3 Algorithms and computational complexity 2 4 Cryptography 3 Publications 4 Notes 5 External linksCareer EditFischer 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 where his students included Rebecca N Wright 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 EditDistributed computing Edit Fischer s 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 Edit In 1980 Fischer and Richard E 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 by Soviet mathematicians 10 11 Algorithms and computational complexity Edit 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 Edit 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 EditGaller Bernard A Fischer Michael J 1964 An improved equivalence algorithm Communications of the ACM 7 5 301 303 doi 10 1145 364099 364331 S2CID 9034016 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 S2CID 13381535 18 Ladner Richard E Fischer Michael J 1980 Parallel prefix computation Journal of the ACM 27 4 831 838 doi 10 1145 322217 322232 S2CID 207568668 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 S2CID 207660233 20 21 Cohen Josh D Fischer Michael J 1985 26th Annual Symposium on Foundations of Computer Science SFCS 1985 26th Annual Symposium on Foundations of Computer Science sfcs 1985 pp 372 382 doi 10 1109 SFCS 1985 2 ISBN 0 8186 0644 4 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 S2CID 6333850 16 Notes Edit Journal of the ACM JACM Volume 30 Issue 1 January 1983 ACM Portal Retrieved 2009 07 06 Journal of the ACM JACM Volume 33 Issue 3 July 1986 ACM Portal Retrieved 2009 07 06 ACM Fellows ACM Archived from the original on 2009 01 01 Retrieved 2009 07 06 ACM Fellows Award Michael J Fischer ACM Retrieved 2009 07 06 For outstanding technical contributions to theoretical computer science and for dedicated service to the computer science community Fischer Lynch amp Paterson 1985 a b PODC Influential Paper Award 2001 Retrieved 2009 07 06 A chronological history of SIGOPS ACM SIGOPS Retrieved 2009 07 06 Twenty Second ACM Symposium on Principles of Distributed Computing PODC 2003 July 13 16 2003 Boston Massachusetts Retrieved 2009 07 06 Ladner amp Fischer 1980 Harwood Aaron 2003 Ladner and Fischer s parallel prefix algorithm Networks and Parallel Processing Complexity Notes Archived from the original on 2016 03 04 Retrieved 2009 07 07 Offman Y P 1962 On the Algorithmic Complexity of Discrete Functions Dokl Sov Acad Sci in Russian 145 1 48 51 English translation in Sov Phys Dokl 7 7 589 591 1963 Krapchenko A N 1970 Asymptotic Estimation of Addition Time of a Parallel Adder Syst Theory Res 19 105 122 a b c Meyer Albert R 12 July 2003 M J Fischer et al the first decade mid 60 s to 70 s PDF Retrieved 2009 07 06 Slides from PODC 2003 Wagner amp Fischer 1974 Galler amp Fischer 1964 Cohen amp Fischer 1985 a b c d Wright Rebecca N 2003 Fischer s cryptographic protocols Proc PODC 2003 pp 20 22 doi 10 1145 872035 872039 Fischer Micali amp Rackoff 1996 originally presented in 1984 1592 citations Google Scholar Retrieved 2009 07 06 726 citations Google Scholar Retrieved 2009 07 07 PODC Influential Paper Award in 2001 2431 citations Google Scholar Retrieved 2009 07 06 External links EditOfficial website nbsp Michael John Fischer at the Mathematics Genealogy Project nbsp Michael J Fischer at DBLP Bibliography Server nbsp Fischer Michael J at zbMATH Fischer Michael J at MathSciNet Retrieved from https en wikipedia org w index php title Michael J Fischer amp oldid 1170130956, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.