Michael Sipser
According to our database^{1},
Michael Sipser
authored at least 47 papers
between 1977 and 2013.
Collaborative distances:
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 OtherLinks
Homepages:

at viaf.org

at id.loc.gov

at dnb.info

at isni.org

at dl.acm.org
On csauthors.net:
Bibliography
2013
AC^{0} Pseudorandomness of Natural Operations.
Electronic Colloquium on Computational Complexity (ECCC), 2013
1997
Retraction of Probabilistic Computation and Linear Time.
Proceedings of the TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Introduction to the theory of computation.
PWS Publishing Company, ISBN: 9780534947286, 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 MultiProver Interactive Protocols.
Theor. Comput. Sci., 1994
Optimal Constructions of Hybrid Algorithms.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 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 MultiProver 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 CONP 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 multipower 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 PolynomialTime Hierarchy.
Mathematical Systems Theory, 1984
Communication Complexity.
J. Comput. Syst. Sci., 1984
On Scheduling UnitLength 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 PolynomialTime Hierarchy
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981
1980
Halting SpaceBounded Computations.
Theor. Comput. Sci., 1980
Lower Bounds on the Size of Sweeping Automata.
J. Comput. Syst. Sci., 1980
GO Is PolynomialSpace 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 SpaceBounded 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