Michael J. Fischer | Academic Influence

Why Is Michael J. Fischer Influential?

(Suggest an Edit or Addition)

By Erik J. Larson, PhD

Areas of Specialization: Cryptography, Algorithms and Data Structures, Computational Complexity
Michael J. Fischer is a computer scientist best known for his work on cryptography, algorithms and data structures, parallel and distributed computing and computational complexity. He earned a B.Sc in mathematics from the University of Michigan and an M.A. and Ph.D. in applied mathematics from Harvard University.

He has spent his career as an assistant professor of computer science at Carnegie Mellon University, of mathematics at the Massachusetts Institute of Technology, an associate professor of electrical engineering and a professor of computer science at the University of Washington and Yale University.

His computer science research work has yielded important theoretical and practical applications for the creation of parallel algorithms and protocol for oblivious transfer. His most-cited work, “The string-to-string correction problem”, explores methods for string matching and parsing and formal grammars.

With colleagues Nancy Lynch and Michael Paterson, he was awarded the PODC Influential-Paper Award for their work on consensus problems. Their research found that if one processor crashes, consensus will be impossible.

Fischer also served as the editor-in-chief for the Journal of the ACM from 1982 to 1986 and is a fellow of the Association for Computing Machinery. Today, he teaches courses in cryptography and computer security, object-oriented programming and internet-scale applications.

Academic Website

Featured in Top Influential Computer Scientists Today

According to Wikipedia, Michael John Fischer 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.

(See a Problem?)

Michael J. Fischer's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Papers

The String-to-String Correction Problem (1974) (3220)
Impossibility of distributed consensus with one faulty process (1983) (2685)
Impossibility of distributed consensus with one faulty process (1985) (2526)
Propositional Dynamic Logic of Regular Programs (1979) (1312)
Parallel Prefix Computation (1980) (879)
Computation in networks of passively mobile finite-state sensors (2004) (551)
A Lower Bound for the Time to Assure Interactive Consistency (1982) (514)
A robust and verifiable cryptographically secure election scheme (1985) (499)
STRING-MATCHING AND OTHER PRODUCTS (1974) (459)
The Consensus Problem in Unreliable Distributed Systems (A Brief Survey) (1983) (396)
SUPER-EXPONENTIAL COMPLEXITY OF PRESBURGER ARITHMETIC (1974) (395)
Relations Among Complexity Measures (1979) (373)
Easy impossibility proofs for distributed consensus problems (1985) (263)
Grammars with Macro-Like Productions (1968) (224)
Boolean Matrix Multiplication and Transitive Closure (1971) (196)
Scalable Bias-Resistant Distributed Randomness (2017) (184)
Separating Nondeterministic Time Complexity Classes (1978) (173)
Lambda-calculus schemata (1993) (160)
Sacrificing serializability to attain high availability of data in an unreliable network (1982) (158)
Propositional modal logic of programs (1977) (154)
Economical solutions for the critical section problem in a distributed system (Extended Abstract) (1977) (146)
Self-stabilizing population protocols (2005) (145)
An Efficient Algorithm for Byzantine Agreement without Authentication (1982) (132)
The architecture of the Eden system (1981) (116)
Resource allocation with immunity to limited process failure (1979) (110)
Self-stabilizing Leader Election in Networks of Finite-State Anonymous Agents (2006) (105)
Global States of a Distributed System (1982) (104)
On Describing the Behavior and Implementation of Distributed Systems (1979) (94)
Stably Computable Properties of Network Graphs (2005) (91)
A time-space tradeoff for sorting on non-oblivious machines (1979) (89)
Distributed FIFO allocation of identical resources using small shared space (1985) (87)
Finding a Majority Among N Votes. (1982) (75)
Reliable communication over unreliable channels (1994) (74)
Foundations of Knowledge for Distributed Systems (1986) (72)
Efficiency of Synchronous Versus Asynchronous Distributed Systems (1983) (62)
Simple and efficient Byzantine generals algorithm (1982) (62)
Assigning tasks for efficiency in Hadoop: extended abstract (2010) (58)
Bounds on secret key exchange using a random deal of cards (1996) (57)
Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable (1982) (56)
Some properties of precedence languages (1969) (53)
Stabilizing Consensus in Mobile Networks (2006) (50)
Multiparty Secret Key Exchange Using a Random Deal of Cards (1991) (49)
Efficiency of Equivalence Algorithms (1972) (46)
Hauptvortrag: The complexity of negation-limited networks - A brief survey (1975) (45)
The wakeup problem (1990) (42)
An Application of Game-Theoretic Techniques to Cryptography (1990) (40)
AN IMPROVED OVERLAP ARGUMENT FOR ON-LINE MULTIPLICATION (1974) (38)
A simple game for the study of trust in distributed systems (2001) (34)
Fast on-line integer multiplication (1973) (33)
Omega(n log n) Lower Bounds on Length of Boolean Formulas (1982) (32)
Secret Bit Transmission Using a Random Deal of Cards (1990) (31)
Efficient fault tolerant routings in networks (1984) (27)
Two Characterizations of the Context-Sensitive Languages (1969) (26)
A secure protocol for the oblivious transfer (extended abstract) (1996) (25)
Reasoning about Uncertainty in Fault-tolerant Distributed Systems (1988) (24)
Efficient Fault-Tolerant Routings in Networks (1987) (24)
Proceedings of the tenth annual ACM symposium on Theory of computing (1978) (23)
An efficient protocol for unconditionally secure secret key exchange (1993) (23)
Appraising two decades of distributed computing theory research (2003) (22)
A public randomness service (2011) (21)
Assigning Tasks for Efficiency in Hadoop ∗ (2010) (20)
Fishspear: a priority queue algorithm (1994) (19)
A difference in efficiency between synchronous and asynchronous systems (1981) (19)
Limited Random Access Turing Machines (1968) (16)
Optimal tree layout (Preliminary Version) (1980) (16)
Distributed systems of simple interacting agents (2007) (16)
Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse (1987) (15)
A time-space tradeoff for sorting and related non-oblivious computations (1979) (14)
A Theoretician's View of Fault Tolerant Distributed Computing (1986) (13)
Shared data requirements for implementation of mutual exclusion using a test-and-set primitive (1978) (13)
Probabilistic Analysis of a Network Resource Allocation Algorithm (1985) (13)
Modes of presentation for on-line help: full screen, split screen and windowed formats (1989) (11)
Space-Efficient Asynchronous Consensus Without Shared Memory Initialization (1993) (10)
Lower bounds on the size of Boolean formulas: Preliminary Report (1975) (10)
Secure sealed-bid online auctions using discreet cryptographic proofs (2013) (9)
Multimodality serial follow-up of thoracic aortic aneurysms (1997) (9)
Deniable Anonymous Group Authentication (2014) (7)
Towards understanding the predictability of stock markets from the perspective of computational complexity (2000) (7)
Storage Requirements for Fair Scheduling (1983) (7)
Real-time solutions of the origin-crossing problem (1968) (7)
Private eyes: Secure remote biometric authentication (2015) (6)
Optimal Placement of Identical Resources in a Distributed Network (1981) (6)
Achieving perfect secrecy using correlated random variables (1994) (5)
A Technique for Decomposing Algorithms Which Use a Single Shared Variable (1983) (5)
Stabilization, Safety, and Security of Distributed Systems: 12th International Symposium, SSS 2010, New York, NY, USA, September 20-22, 2010. Proceedings (2010) (5)
The Complexity of Negation-Limited Networks-A Brief Survey t (2005) (5)
Sets that don't help (1973) (4)
Relative Knowledge and Belief (Extended Abstract). (1987) (4)
Decision Making in the Presence of Noise (1992) (4)
Mode modules as representations of domains: preliminary report (1973) (4)
The iteration element (1965) (3)
Incentives Don't Solve Blockchain's Problems (2019) (3)
Fishspear: A Priority Queue Algorithm (Extended Abstract) (1984) (3)
Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing (1982) (3)
Uncertain Knowledge in Distributed Systems. (1988) (2)
Strong Theft-Proof Privacy-Preserving Biometric Authentication (2012) (2)
Proceedings of the 12th international conference on Stabilization, safety, and security of distributed systems (2010) (2)
Efficient and Privacy-Preserving Biometric Authentication ∗ (2013) (2)
On computing weak transitive closure on O(log N) expected random parallel time (1982) (2)
Efficient fault-tolerant infrastructure for cloud computing (2013) (2)
Evolution of distributed computing theory: from concurrency to networks and beyond (2008) (2)
Optimal Placement of Identical Resources in a Tree (1992) (2)
Dynamic monotone priorities on planar sets (1985) (2)
On Developing a Theory of Distributed Computing: Summary of Current Research. (1980) (2)
A Review of Civil War Tax Legislation and Its Influence on the Current U.S. Income Tax System (2006) (1)
On Backtracking Resistance in Pseudorandom Bit Generation ∗ (2012) (1)
Poster : Scalable Bias-Resistant Distributed Randomness (2017) (1)
A LOWER BOUND FOB THE TIME TO ASSUBE INTEBACTIVE CONSiSTENCV (1982) (1)
CPSC 467 a : Cryptography and Computer Security (2006) (0)
A Report on AMBIT/G. Volume 1 (1971) (0)
The Wakeup Problem * • ( DRAFT ) (2014) (0)
Cpsc 461b: Foundations of Cryptography Notes 22 (rev. 1) Lecture Notes 22 58 Simple Application of Oblivious Transfer 59 Private Circuit Evaluation Using Shares (0)
Lecture Notes 19 47 a Zero-knowledge Interactive Proof for Graph 3-coloring (0)
Lecture Notes 24 114 Bit Commitment Using Hash Functions (2008) (0)
Dynamic Monotone Priorities on Planar Sets (Extended Abstract) (1985) (0)
CORACT OR GRANT NUMBE() (1990) (0)
Lecture Notes 18 45 Recapitulation of Lecture 17 45.1 Zero Knowledge Interactive Proof for Graph Isomorphism (0)
Estimating Parameters of Monotone Boolean Functions (Abstract) (1998) (0)
Lecture Notes 10 23 Analyzing the Success Probability (0)
New Haven , CT 06520 – 8285 Urn Automata (2006) (0)
Zero Knowledge Interactive Proof Systems (0)
Optimal Layout of Edge-weighted Forests (1999) (0)
Optimal Resource Placement in a Distributed System. (Extended Abstract). (1980) (0)
Cpsc 461b: Foundations of Cryptography Notes 21 (rev. 1) Lecture Notes 21 53 the Millionaire's Problem (2009) (0)
Lecture Notes 8 39 Exponentiation : Speeding up the Computation (2006) (0)
Further Remarks on Bit-Commitment 49 . 1 Prediction Versus Distinguishability (0)
Special SIGACT issue (1972) (0)
Contents Vol. 36, 2012 (2012) (0)
Yale University Department of Computer Science Private Eyes : Secure Remote Biometric Authentication (2015) (0)
Societies of randomly interacting finite-state automata (2004) (0)
Irene K. Fischer (1907-2009) (2010) (0)
Cpsc 467b: Cryptography and Computer Security Handout #2 Problem Set 1 (0)
CPSC 467 a : Cryptography and Computer Security Notes (2005) (0)
Assigning Tasks for Efficiency in Hadoop [ Extended (2010) (0)
Assigning Tasks for Efficiency in Hadoop [ Extended (2010) (0)
The Wakeup Problem (Extended Abstract) (1990) (0)
The Colored Ticket Algorithm. (1983) (0)
Fishspear: A Priority Queue Algorithm1 (EXTENDED (1984) (0)
Priority Arguments in Complexity Theory (1972) (0)
Pseudorandom Sequence Generation 1 Distinguishability and Bit Prediction (0)
Cpsc 461b: Foundations of Cryptography Notes 8 (rev. 1) (0)
Parallel Algorithms for Shared-memory Machines. a Standard Wasteful Implementation (1996) (0)

This paper list is powered by the following services:

Other Resources About Michael J. Fischer

What Schools Are Affiliated With Michael J. Fischer?

Michael J. Fischer is affiliated with the following schools:

Michael J. Fischer's AcademicInfluence.com Rankings

Computer Science