Michael John Fischer (born 1942) is a

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus ( ...

who works in the fields of

distributed computing A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...

, parallel computing,

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s and

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...

s, and

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

Career

Fischer was born in 1942 in

Ann Arbor Anne, alternatively spelled Ann, is a form of the Latin female given name Anna. This in turn is a representation of the Hebrew Hannah, which means 'favour' or 'grace'. Related names include Annie. Anne is sometimes used as a male name in the ...

Michigan Michigan () is a U.S. state, state in the Great Lakes region, Great Lakes region of the Upper Midwest, upper Midwestern United States. With a population of nearly 10.12 million and an area of nearly , Michigan is the List of U.S. states and ...

, USA. He received his

BSc A Bachelor of Science (BS, BSc, SB, or ScB; from the Latin ') is a bachelor's degree awarded for programs that generally last three to five years. The first university to admit a student to the degree of Bachelor of Science was the University of ...

degree in mathematics from the

University of Michigan , mottoeng = "Arts, Knowledge, Truth" , former_names = Catholepistemiad, or University of Michigania (1817–1821) , budget = $10.3 billion (2021) , endowment = $17 billion (2021)As o ...

in 1963. Fischer did his MA and

PhD PHD or PhD may refer to: * Doctor of Philosophy (PhD), an academic qualification Entertainment * '' PhD: Phantasy Degree'', a Korean comic series * ''Piled Higher and Deeper ''Piled Higher and Deeper'' (also known as ''PhD Comics''), is a newsp ...

studies in

applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemat ...

Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of high ...

; he received his MA degree in 1965 and PhD in 1968. Fischer's PhD supervisor at Harvard was

Sheila Greibach Sheila Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los ...

. After receiving his PhD, Fischer was an assistant professor of computer science at

Carnegie-Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technol ...

in 1968–1969, an assistant professor of mathematics at

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private Land-grant university, land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern t ...

(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 Frances Foong Chu Yao () is a Chinese-born American mathematician and theoretical computer scientist. She is currently a Chair Professor at the Institute for Interdisciplinary Information Sciences (IIIS) of Tsinghua University. She was Chair Pro ...

, and Michael Hammer. In 1975, Fischer was nominated as a professor of

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

at the

University of Washington The University of Washington (UW, simply Washington, or informally U-Dub) is a public research university in Seattle, Washington. Founded in 1861, Washington is one of the oldest universities on the West Coast; it was established in Seat ...

. Since 1981, he has been a professor of computer science at

Yale University Yale University is a Private university, private research university in New Haven, Connecticut. Established in 1701 as the Collegiate School, it is the List of Colonial Colleges, third-oldest institution of higher education in the United Sta ...

, where his students included Rebecca N. Wright. Fischer served as the editor-in-chief of the

Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief An editor-in-c ...

in 1982–1986. He was inducted as a Fellow of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

(ACM) in 1996.

Work

Distributed computing

Fischer's 1985 work with Nancy A. Lynch and

Michael S. Paterson Michael Stewart Paterson, is a British computer scientist, who was the director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick until 2007, and chair of the department of computer science in 200 ...

on consensus problems received the

PODC Influential-Paper Award The Edsger W. Dijkstra Paper Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at lea ...

in 2001. 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.” Fischer was the program chairman of the first

Symposium on Principles of Distributed Computing The Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery (special interest groups SIGACT and SIGOPS). Scope and re ...

(PODC) in 1982; 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, with

Leslie Lamport Leslie B. Lamport (born February 7, 1941 in Brooklyn) is an American computer scientist and mathematician. Lamport is best known for his seminal work in distributed systems, and as the initial developer of the document preparation system LaTeX and ...

, Nancy Lynch, Albert R. Meyer, and Rebecca Wright as speakers.

Parallel computing

In 1980, Fischer and Richard E. Ladner presented a

parallel algorithm In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machine ...

for computing

prefix sum In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers is a second sequence of numbers , the sums of prefixes (running totals) of the input sequence: : : : :... For instance, the prefix sums of ...

s 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. However, the same circuit designs were already studied much earlier by

Soviet The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen national ...

mathematicians.. English translation in ''Sov. Phys. Dokl.'' 7 (7): 589–591 1963..

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 Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...

and

formal grammar In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe ...

s. Slides from PODC 2003. One of Fischer's most-cited works deals with

string matching In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger strin ...

. Already during his years at Michigan, Fischer studied disjoint-set data structures together with

Bernard Galler Bernard A. Galler ( in Chicago – in Ann Arbor, Michigan) was an American mathematician and computer scientist at the University of Michigan who was involved in the development of large-scale operating systems and computer languages includ ...

Cryptography

Fischer is one of the pioneers in

electronic voting Electronic voting (also known as e-voting) is voting that uses electronic means to either aid or take care of casting and counting ballots. Depending on the particular implementation, e-voting may use standalone '' electronic voting machines'' ...

. In 1985, Fischer and his student Josh Cohen Benaloh presented one of the first electronic voting schemes.. Other contributions related to cryptography include the study of

key exchange Key exchange (also key establishment) is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm. If the sender and receiver wish to exchange encrypted messages, each ...

problems and a protocol for oblivious transfer. In 1984, Fischer,

Silvio Micali Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security. In 2012, he receive ...

, and

Charles Rackoff Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, he attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar ...

presented an improved version of

Michael O. Rabin Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award. Biography Early life and education Rabin was born in 1931 in ...

's protocol for oblivious transfer.

Publications

* . * . * . * . * . * .

Notes

External links

* * * *
Fischer, Michael J.
at

MathSciNet MathSciNet is a searchable online bibliographic database created by the American Mathematical Society in 1996. It contains all of the contents of the journal '' Mathematical Reviews'' (MR) since 1940 along with an extensive author database, links ...

{{DEFAULTSORT:Fischer, Michael J. 1942 births Living people Researchers in distributed computing Theoretical computer scientists University of Michigan College of Literature, Science, and the Arts alumni Harvard University alumni Yale University faculty Fellows of the Association for Computing Machinery People from Ann Arbor, Michigan Dijkstra Prize laureates