Michael Sipser

According to our database, Michael Sipser authored at least 37 papers between 1977 and 2013.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2013

AC⁰ Pseudorandomness of Natural Operations.

Zachary Remscrim, Michael Sipser

Electron. Colloquium Comput. Complex., 2013

1997

Retraction of Probabilistic Computation and Linear Time.

Lance Fortnow, Michael Sipser

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Introduction to the theory of computation.

Michael Sipser

PWS Publishing Company, ISBN: 978-0-534-94728-6, 1997

1996

Introduction to the Theory of Computation.

Michael Sipser

SIGACT News, 1996

The future of computational complexity theory: part I.

Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser

SIGACT News, 1996

1995

Monotone Separation of Logarithmic Space from Logarithmic Depth.

Michelangelo Grigni, Michael Sipser

J. Comput. Syst. Sci., 1995

1994

On the Power of Multi-Prover Interactive Protocols.

Lance Fortnow, John Rompel, Michael Sipser

Theor. Comput. Sci., 1994

Optimal Constructions of Hybrid Algorithms.

Ming-Yang Kao, Yuan Ma, Michael Sipser, Yiqun Lisa Yin

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

Expander Codes

Michael Sipser, Daniel A. Spielman

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Inference and Minimization of Hidden Markov Chains.

David Gillman, Michael Sipser

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1992

The History and Status of the P versus NP Question

Michael Sipser

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

Monotone Separation of Logspace from NC.

Michelangelo Grigni, Michael Sipser

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.

Lance Fortnow, John Rompel, Michael Sipser

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

The Complexity of Finite Functions.

Ravi B. Boppana, Michael Sipser

Proceedings of the Handbook of Theoretical Computer Science, 1990

1989

On Completeness and Soundness in Interactive Proof Systems.

Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos

Adv. Comput. Res., 1989

1988

Are There Interactive Protocols for CO-NP Languages?

Lance Fortnow, Michael Sipser

Inf. Process. Lett., 1988

Dynamic Networks Are as Fast as Static Networks (Preliminary Version)

Baruch Awerbuch, Michael Sipser

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

On the power of multi-power interactive protocols.

Lance Fortnow, John Rompel, Michael Sipser

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)

Oded Goldreich, Yishay Mansour, Michael Sipser

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

Private Coins versus Public Coins in Interactive Proof Systems

Shafi Goldwasser, Michael Sipser

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Expanders, Randomness, or Time versus Space.

Michael Sipser

Proceedings of the Structure in Complexity Theory, 1986

1985

Compression and Ranking

Andrew V. Goldberg, Michael Sipser

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

1984

On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals.

Barbara Simons, Michael Sipser

Oper. Res., 1984

A Topological View of Some Problems in Complexity Theory.

Michael Sipser

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Graph Bisection Algorithms with Good Average Case Behavior

Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

A Complexity Theoretic Approach to Randomness

Michael Sipser

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Borel Sets and Circuit Complexity

Michael Sipser

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

Communication Complexity

Christos H. Papadimitriou, Michael Sipser

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

On Relativization and the Existence of Complete Sets.

Michael Sipser

Proceedings of the Automata, 1982

1981

Maximum Matchings in Sparse Random Graphs

Richard M. Karp, Michael Sipser

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

Parity, Circuits, and the Polynomial-Time Hierarchy

Merrick L. Furst, James B. Saxe, Michael Sipser

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

GO Is Polynomial-Space Hard.

David Lichtenstein, Michael Sipser

J. ACM, 1980

1979

Lower Bounds on the Size of Sweeping Automata

Michael Sipser

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978

Nondeterminism and the Size of Two Way Finite Automata

William J. Sakoda, Michael Sipser

Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

Halting Space-Bounded Computations

Michael Sipser

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

GO Is PSPACE Hard

David Lichtenstein, Michael Sipser

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977

Several Results in Program Size Complexity

Howard P. Katseff, Michael Sipser

Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977