Michael J. Fischer

Affiliations:
  • Yale University, New Haven, Connecticut, USA


According to our database1, Michael J. Fischer authored at least 90 papers between 1964 and 2021.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 1996, "For outstanding technical contributions to theoretical computer science, and for dedicated service to the computer science community.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Privacy-Preserving Data Sharing for Medical Research.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2021

2019
Incentives Don't Solve Blockchain's Problems.
Proceedings of the 10th IEEE Annual Ubiquitous Computing, 2019

2016
Scalable Bias-Resistant Distributed Randomness.
IACR Cryptol. ePrint Arch., 2016

2015
Private Eyes: Secure Remote Biometric Authentication.
Proceedings of the SECRYPT 2015, 2015

2013
Secure sealed-bid online auctions using discreet cryptographic proofs.
Math. Comput. Model., 2013

2011
A Public Randomness Service.
Proceedings of the SECRYPT 2011 - Proceedings of the International Conference on Security and Cryptography, Seville, Spain, 18, 2011

2010
Assigning tasks for efficiency in Hadoop: extended abstract.
Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

2008
Self-stabilizing population protocols.
ACM Trans. Auton. Adapt. Syst., 2008

Evolution of distributed computing theory: from concurrency to networks and beyond.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

2006
Computation in networks of passively mobile finite-state sensors.
Distributed Comput., 2006

Self-stabilizing Leader Election in Networks of Finite-State Anonymous Agents.
Proceedings of the Principles of Distributed Systems, 10th International Conference, 2006

Stabilizing Consensus in Mobile Networks.
Proceedings of the Distributed Computing in Sensor Systems, 2006

2005
Stably Computable Properties of Network Graphs.
Proceedings of the Distributed Computing in Sensor Systems, 2005

2003
JACM 1983-1986.
J. ACM, 2003

Appraising two decades of distributed computing theory research.
Distributed Comput., 2003

2001
Towards understanding the predictability of stock markets from the perspective of computational complexity.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

1999
Optimal Layout of Edge-weighted Forests.
Discret. Appl. Math., 1999

1998
Estimating Parameters of Monotone Boolean Functions (Abstract).
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

1996
The Wakeup Problem.
SIAM J. Comput., 1996

Bounds on Secret Key Exchange Using a Random Deal of Cards.
J. Cryptol., 1996

A Secure Protocol for the Oblivious Transfer (Extended Abstract).
J. Cryptol., 1996

1994
Fishspear: A Priority Queue Algorithm.
J. ACM, 1994

Reliable Communication Over Unreliable Channels.
J. ACM, 1994

1993
Lambda-Calculus Schemata.
LISP Symb. Comput., 1993

Space-Efficient Asynchronous Consensus Without Shared Memory Initialization.
Inf. Process. Lett., 1993

An Efficient Protocol for Unconditionally Secure Secret Key Exchange.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

1992
Optimal Placement of Identical Resources in a Tree
Inf. Comput., January, 1992

Decision Making in the Presence of Noise.
Proceedings of the Informatik, Festschrift zum 60. Geburtstag von Günter Hotz, 1992

1991
Multiparty Secret Key Exchange Using a Random Deal of Cards.
Proceedings of the Advances in Cryptology, 1991

1990
The Wakeup Problem (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

An Application of Game-Theoretic Techniques to Cryptography.
Proceedings of the Advances In Computational Complexity Theory, 1990

1989
Distributed FIFO Allocation of Identical Resources Using Small Shared Space.
ACM Trans. Program. Lang. Syst., 1989

Primitive recursion without implicit predecessor.
SIGACT News, 1989

Secret Bit Transmission Using a Random Deal of Cards.
Proceedings of the Distributed Computing And Cryptography, 1989

1988
Reasoning about Uncertainty in Fault-tolerant Distributed Systems.
Proceedings of the Formal Techniques in Real-Time and Fault-Tolerant Systems, 1988

1987
Efficient Fault-Tolerant Routings in Networks
Inf. Comput., October, 1987

Interpreting Logics of Knowledge in Propositional Dynamic Logic with Converse.
Inf. Process. Lett., 1987

1986
Probabilistic Analysis of a Network Resource Allocation Algorithm
Inf. Control., 1986

Easy Impossibility Proofs for Distributed Consensus Problems.
Distributed Comput., 1986

Foundations of Knowledge for Distributed Systems.
Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

A Theoretician's View of Fault Tolerant Distributed Computing.
Proceedings of the Fault-Tolerant Distributed Computing [Asilomar Workshop 1986], 1986

1985
Impossibility of Distributed Consensus with One Faulty Process
J. ACM, April, 1985

Dynamic Monotone Priorities on Planar Sets (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

A Robust and Verifiable Cryptographically Secure Election Scheme (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Fishspear: A Priority Queue Algorithm (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Efficiency of Synchronous Versus Asynchronous Distributed Systems
J. ACM, July, 1983

A Technique for Decomposing Algorithms Which Use a Single Shared Variable.
J. Comput. Syst. Sci., 1983

Storage Requirements for Fair Scheduling.
Inf. Process. Lett., 1983

The Consensus Problem in Unreliable Distributed Systems (A Brief Survey).
Proceedings of the Fundamentals of Computation Theory, 1983

1982
An Efficient Algorithm for Byzantine Agreement without Authentication
Inf. Control., March, 1982

Global States of a Distributed System.
IEEE Trans. Software Eng., 1982

Omega(n log n) Lower Bounds on Length of Boolean Formulas.
SIAM J. Comput., 1982

Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable.
J. ACM, 1982

A Lower Bound for the Time to Assure Interactive Consistency.
Inf. Process. Lett., 1982

Sacrificing Serializability to Attain High Availability of Data.
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

On computing weak transitive closure on O(log N) expected random parallel time.
Proceedings of the International Conference on Parallel Processing, 1982

1981
On Describing the Behavior and Implementation of Distributed Systems.
Theor. Comput. Sci., 1981

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.
J. Comput. Syst. Sci., 1981

A Difference in Efficiency between Synchronous and Asynchronous Systems
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

The Architecture of the Eden System.
Proceedings of the Eighth Symposium on Operating System Principles, 1981

Optimal Placement of Identical Resources in a Distributed Network.
Proceedings of the 2nd International Conference on Distributed Computing Systems, 1981

1980
Parallel Prefix Computation.
J. ACM, 1980

Optimal Tree Layout (Preliminary Version)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
A time-space tradeoff for sorting and related non-oblivious computations.
SIGACT News, 1979

Propositional Dynamic Logic of Regular Programs.
J. Comput. Syst. Sci., 1979

Relations Among Complexity Measures.
J. ACM, 1979

Resource Allocation with Immunity to Limited Process Failure (Preliminary Report)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Separating Nondeterministic Time Complexity Classes.
J. ACM, 1978

1977
Economical Solutions for the Critical Section Problem in a Distributed System (Extended Abstract)
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

Propositional Modal Logic of Programs (Extended Abstract)
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

1976
A Note on the Average Time to Compute Transitive Closures.
Proceedings of the Third International Colloquium on Automata, 1976

1975
Lower Bounds on the Size of Boolean Formulas: Preliminary Report
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

Hauptvortrag: The complexity of negation-limited networks - A brief survey.
Proceedings of the Automata Theory and Formal Languages, 1975

1974
Fast On-Line Integer Multiplication.
J. Comput. Syst. Sci., 1974

The String-to-String Correction Problem.
J. ACM, 1974

1973
A note on disjunctive form tautologies.
SIGACT News, 1973

Sets that Don't Help
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973

Mode Modules as Representations of Domains.
Proceedings of the Conference Record of the ACM Symposium on Principles of Programming Languages, 1973

Refinements of the Nondeterministic Time and Space Hierarchies
Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973

1972
Efficiency of Equivalence Algorithms.
Proceedings of a symposium on the Complexity of Computer Computations, 1972

1971
Economy of Description by Automata, Grammars, and Formal Systems
Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971

Boolean Matrix Multiplication and Transitive Closure
Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971

1969
Some Properties of Precedence Languages
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969

Two Characterizations of the Context-Sensitive Languages
Proceedings of the 10th Annual Symposium on Switching and Automata Theory, 1969

1968
Real-Time Solutions of the Origin-Crossing Problem.
Math. Syst. Theory, 1968

Limited Random Access Turing Machines
Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968

Grammars with Macro-Like Productions
Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968

1965
The iteration element.
Commun. ACM, 1965

1964
In defense of the equivalence algorithm.
Commun. ACM, 1964

An improved equivalence algorithm.
Commun. ACM, 1964


  Loading...