Michael Sipser

According to our database, Michael Sipser authored at least 37 papers between 1978 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

1998

Optimal Constructions of Hybrid Algorithms.

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

J. Algorithms, 1998

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

Expander codes.

Michael Sipser, Daniel A. Spielman

IEEE Trans. Inf. Theory, 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

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

Compression and Ranking.

Andrew V. Goldberg, Michael Sipser

SIAM J. Comput., 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

Private Coins versus Public Coins in Interactive Proof Systems.

Shafi Goldwasser, Michael Sipser

Adv. Comput. Res., 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

Expanders, Randomness, or Time versus Space.

Michael Sipser

J. Comput. Syst. Sci., 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

Graph bisection algorithms with good average case behavior.

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

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

1984

Parity, Circuits, and the Polynomial-Time Hierarchy.

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

Math. Syst. Theory, 1984

Communication Complexity.

Christos H. Papadimitriou, Michael Sipser

J. Comput. Syst. Sci., 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

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

On Relativization and the Existence of Complete Sets.

Michael Sipser

Proceedings of the Automata, 1982

1981

Several Results in Program Size Complexity.

Howard P. Katseff, Michael Sipser

Theor. Comput. Sci., 1981

Maximum Matchings in Sparse Random Graphs

Richard M. Karp, Michael Sipser

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

1980

Halting Space-Bounded Computations.

Michael Sipser

Theor. Comput. Sci., 1980

Lower Bounds on the Size of Sweeping Automata.

Michael Sipser

J. Comput. Syst. Sci., 1980

GO Is Polynomial-Space Hard.

David Lichtenstein, Michael Sipser

J. ACM, 1980

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

GO Is PSPACE Hard

David Lichtenstein, Michael Sipser

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