Michael Sipser

According to our database1, Michael Sipser authored at least 47 papers between 1977 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

Homepages:

On csauthors.net:

Bibliography

2013
AC0 Pseudorandomness of Natural Operations.
Electronic Colloquium on Computational Complexity (ECCC), 2013

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. Information 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

Optimal Constructions of Hybrid Algorithms.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Expander Codes
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 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, Chicago, Illinois, USA, June 30, 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.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), 1990

1989
Private Coins versus Public Coins in Interactive Proof Systems.
Advances in Computing Research, 1989

On Completeness and Soundness in Interactive Proof Systems.
Advances in Computing Research, 1989

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

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.
Combinatorica, 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

1986
Private Coins versus Public Coins in Interactive Proof Systems
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Expanders, Randomness, or Time versus Space.
Proceedings of the Structure in Complexity Theory, 1986

1985
Compression and Ranking
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

1984
Parity, Circuits, and the Polynomial-Time Hierarchy.
Mathematical Systems Theory, 1984

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

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

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

Graph Bisection Algorithms with Good Average Case Behavior
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 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
Communication Complexity
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 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

Parity, Circuits, and the Polynomial-Time Hierarchy
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

1979
Lower Bounds on the Size of Sweeping Automata
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

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

Halting Space-Bounded Computations
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

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

1977
Several Results in Program Size Complexity
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977


  Loading...