Michael Sipser

50 papers A* 21B 1Journal 21Unranked 4

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