`Travelled to:`

1 × Canada

1 × Denmark

8 × USA

`Collaborated with:`

∅ L.Fortnow S.Goldwasser A.V.Goldberg C.H.Papadimitriou W.J.Sakoda

`Talks about:`

complex (3) probabilist (2) automata (2) versus (2) linear (2) comput (2) time (2) size (2) coin (2) set (2)

## Person: Michael Sipser

### DBLP: Sipser:Michael

### Contributed to:

### Wrote 11 papers:

- STOC-1997-FortnowS #linear #probability
- Retraction of Probabilistic Computation and Linear Time (LF, MS), p. 750.
- STOC-1992-Sipser
- The History and Status of the P versus NP Question (MS), pp. 603–618.
- STOC-1989-FortnowS #linear #probability
- Probabilistic Computation and Linear Time (LF, MS), pp. 148–156.
- STOC-1986-GoldwasserS #interactive #proving
- Private Coins versus Public Coins in Interactive Proof Systems (SG, MS), pp. 59–68.
- STOC-1985-GoldbergS #ranking
- Compression and Ranking (AVG, MS), pp. 440–448.
- STOC-1983-Sipser #complexity #set
- Borel Sets and Circuit Complexity (MS), pp. 61–69.
- STOC-1983-Sipser83a #approach #complexity
- A Complexity Theoretic Approach to Randomness (MS), pp. 330–335.
- ICALP-1982-Sipser #on the #set
- On Relativization and the Existence of Complete Sets (MS), pp. 523–531.
- STOC-1982-PapadimitriouS #communication #complexity
- Communication Complexity (CHP, MS), pp. 196–200.
- STOC-1979-Sipser #automaton #bound
- Lower Bounds on the Size of Sweeping Automata (MS), pp. 360–364.
- STOC-1978-SakodaS #automaton #finite #nondeterminism
- Nondeterminism and the Size of Two Way Finite Automata (WJS, MS), pp. 275–286.