Michael Sipser

Publication Activity (10 Years)

Years Active: 1977-2013
Publications (10 Years): 0

Top Topics

Logical Operations

Processing Units

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Zachary Remscrim, Michael Sipser
Pseudorandomness of Natural Operations. Electron. Colloquium Comput. Complex. 20 (2013)
Ming-Yang Kao, Yuan Ma, Michael Sipser, Yiqun Lisa Yin
Optimal Constructions of Hybrid Algorithms CoRR (2001)
Ming-Yang Kao, Yuan Ma, Michael Sipser, Yiqun Lisa Yin
Optimal Constructions of Hybrid Algorithms. J. Algorithms 29 (1) (1998)
Lance Fortnow, Michael Sipser
Retraction of Probabilistic Computation and Linear Time. STOC (1997)
Michael Sipser, Daniel A. Spielman
Expander codes. IEEE Trans. Inf. Theory 42 (6) (1996)
Michael Sipser
Introduction to the Theory of Computation. SIGACT News 27 (1) (1996)
Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser
The future of computational complexity theory: part I. SIGACT News 27 (3) (1996)
Michelangelo Grigni, Michael Sipser
Monotone Separation of Logarithmic Space from Logarithmic Depth. J. Comput. Syst. Sci. 50 (3) (1995)
David Gillman, Michael Sipser
Inference and Minimization of Hidden Markov Chains. COLT (1994)
Michael Sipser, Daniel A. Spielman
Expander Codes FOCS (1994)
Lance Fortnow, John Rompel, Michael Sipser
On the Power of Multi-Prover Interactive Protocols. Theor. Comput. Sci. 134 (2) (1994)
Ming-Yang Kao, Yuan Ma, Michael Sipser, Yiqun Lisa Yin
Optimal Constructions of Hybrid Algorithms. SODA (1994)
Michael Sipser
The History and Status of the P versus NP Question STOC (1992)
Andrew V. Goldberg, Michael Sipser
Compression and Ranking. SIAM J. Comput. 20 (3) (1991)
Michelangelo Grigni, Michael Sipser
Monotone Separation of Logspace from NC. Computational Complexity Conference (1991)
Lance Fortnow, John Rompel, Michael Sipser
Errata for On the Power of Multi-Prover Interactive Protocols. Computational Complexity Conference (1990)
Shafi Goldwasser, Michael Sipser
Private Coins versus Public Coins in Interactive Proof Systems. Adv. Comput. Res. 5 (1989)
Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos
On Completeness and Soundness in Interactive Proof Systems. Adv. Comput. Res. 5 (1989)
Lance Fortnow, John Rompel, Michael Sipser
On the power of multi-power interactive protocols. Computational Complexity Conference (1988)
Michael Sipser
Expanders, Randomness, or Time versus Space. J. Comput. Syst. Sci. 36 (3) (1988)
Lance Fortnow, Michael Sipser
Are There Interactive Protocols for CO-NP Languages? Inf. Process. Lett. 28 (5) (1988)
Baruch Awerbuch, Michael Sipser
Dynamic Networks Are as Fast as Static Networks (Preliminary Version) FOCS (1988)
Oded Goldreich, Yishay Mansour, Michael Sipser
Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract) FOCS (1987)
Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser
Graph bisection algorithms with good average case behavior. Comb. 7 (2) (1987)
Michael Sipser
Expanders, Randomness, or Time versus Space. Computational Complexity Conference (1986)
Shafi Goldwasser, Michael Sipser
Private Coins versus Public Coins in Interactive Proof Systems STOC (1986)
Andrew V. Goldberg, Michael Sipser
Compression and Ranking STOC (1985)
Christos H. Papadimitriou, Michael Sipser
Communication Complexity. J. Comput. Syst. Sci. 28 (2) (1984)
Barbara Simons, Michael Sipser
On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals. Oper. Res. 32 (1) (1984)
Michael Sipser
A Topological View of Some Problems in Complexity Theory. MFCS (1984)
Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser
Graph Bisection Algorithms with Good Average Case Behavior FOCS (1984)
Merrick L. Furst, James B. Saxe, Michael Sipser
Parity, Circuits, and the Polynomial-Time Hierarchy. Math. Syst. Theory 17 (1) (1984)
Michael Sipser
A Complexity Theoretic Approach to Randomness STOC (1983)
Michael Sipser
Borel Sets and Circuit Complexity STOC (1983)
Michael Sipser
On Relativization and the Existence of Complete Sets. ICALP (1982)
Christos H. Papadimitriou, Michael Sipser
Communication Complexity STOC (1982)
Howard P. Katseff, Michael Sipser
Several Results in Program Size Complexity. Theor. Comput. Sci. 15 (1981)
Merrick L. Furst, James B. Saxe, Michael Sipser
Parity, Circuits, and the Polynomial-Time Hierarchy FOCS (1981)
Richard M. Karp, Michael Sipser
Maximum Matchings in Sparse Random Graphs FOCS (1981)
David Lichtenstein, Michael Sipser
GO Is Polynomial-Space Hard. J. ACM 27 (2) (1980)
Michael Sipser
Lower Bounds on the Size of Sweeping Automata. J. Comput. Syst. Sci. 21 (2) (1980)
Michael Sipser
Halting Space-Bounded Computations. Theor. Comput. Sci. 10 (1980)
Michael Sipser
Lower Bounds on the Size of Sweeping Automata STOC (1979)
David Lichtenstein, Michael Sipser
GO Is PSPACE Hard FOCS (1978)
William J. Sakoda, Michael Sipser
Nondeterminism and the Size of Two Way Finite Automata STOC (1978)
Michael Sipser
Halting Space-Bounded Computations FOCS (1978)
Howard P. Katseff, Michael Sipser
Several Results in Program Size Complexity FOCS (1977)