Michael Sipser

According to our database1, Michael Sipser authored at least 38 papers between 1978 and 2013.

Collaborative distances:

Awards

ACM Fellow

ACM Fellow 2017, "For contributions to computational complexity, particularly randomized computation and circuit complexity".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2013
AC<sup>0</sup> Pseudorandomness of Natural Operations.
Electron. Colloquium Comput. Complex., 2013

1998
Optimal Constructions of Hybrid Algorithms.
J. Algorithms, 1998

1997
Retraction of Probabilistic Computation and Linear Time.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Introduction to the theory of computation.
PWS Publishing Company, ISBN: 978-0-534-94728-6, 1997

1996
Expander codes.
IEEE Trans. Inf. Theory, 1996

Introduction to the Theory of Computation.
SIGACT News, 1996

The future of computational complexity theory: part I.
SIGACT News, 1996

1995
Monotone Separation of Logarithmic Space from Logarithmic Depth.
J. Comput. Syst. Sci., 1995

1994
On the Power of Multi-Prover Interactive Protocols.
Theor. Comput. Sci., 1994

Inference and Minimization of Hidden Markov Chains.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1992
The History and Status of the P versus NP Question
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991
Compression and Ranking.
SIAM J. Comput., 1991

Monotone Separation of Logspace from NC.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991

1990
Errata for On the Power of Multi-Prover Interactive Protocols.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

The Complexity of Finite Functions.
Proceedings of the Handbook of Theoretical Computer Science, 1990

1989
Private Coins versus Public Coins in Interactive Proof Systems.
Adv. Comput. Res., 1989

On Completeness and Soundness in Interactive Proof Systems.
Adv. Comput. Res., 1989

Probabilistic Computation and Linear Time
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
Expanders, Randomness, or Time versus Space.
J. Comput. Syst. Sci., 1988

Are There Interactive Protocols for CO-NP Languages?
Inf. Process. Lett., 1988

Dynamic Networks Are as Fast as Static Networks (Preliminary Version)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

On the power of multi-power interactive protocols.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Graph bisection algorithms with good average case behavior.
Comb., 1987

Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1984
Parity, Circuits, and the Polynomial-Time Hierarchy.
Math. Syst. Theory, 1984

Communication Complexity.
J. Comput. Syst. Sci., 1984

On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals.
Oper. Res., 1984

A Topological View of Some Problems in Complexity Theory.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

1983
A Complexity Theoretic Approach to Randomness
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Borel Sets and Circuit Complexity
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
On Relativization and the Existence of Complete Sets.
Proceedings of the Automata, 1982

1981
Several Results in Program Size Complexity.
Theor. Comput. Sci., 1981

Maximum Matchings in Sparse Random Graphs
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
Halting Space-Bounded Computations.
Theor. Comput. Sci., 1980

Lower Bounds on the Size of Sweeping Automata.
J. Comput. Syst. Sci., 1980

GO Is Polynomial-Space Hard.
J. ACM, 1980

1978
Nondeterminism and the Size of Two Way Finite Automata
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

GO Is PSPACE Hard
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978


  Loading...