Sotabase

Career

· Dean of Science, Massachusetts Institute of Technology (MIT)2013–2020
· Head of the Mathematics Department, Massachusetts Institute of Technology (MIT)2004–2014
· Chair of Applied Mathematics, Massachusetts Institute of Technology (MIT)1998–2000
· Professor, University of California at Berkeley1985–1986
· Research Staff Member, IBM Research1980–2020
· Donner Professor of Mathematics, Massachusetts Institute of Technology (MIT)1980–
· PhD in Engineering, University of California/Berkeley1980–
· Research Assistant, Massachusetts Institute of Technology (MIT)1979–1980
· BA in Mathematics, Cornell University1974–

Publications (131)

Quantum Computation by Adiabatic Evolution
2000
1,729
cited
Introduction to the Theory of Computation
SIGA · 1996
1,615
cited
Parity, circuits, and the polynomial-time hierarchy
22nd Annual Symposium on Foundations of Computer Science (sfcs 1981) · 1981
1,226
cited
Private coins versus public coins in interactive proof systems
Symposium on the Theory of Computing · 1986
573
cited
A complexity theoretic approach to randomness
Symposium on the Theory of Computing · 1983
517
cited
Graph bisection algorithms with good average case behavior
Comb. · 1984
386
cited
The Complexity of Finite Functions
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity · 1991
322
cited
On the Power of Multi-Prover Interactive Protocols
Theoretical Computer Science · 1994
260
cited
Maximum Matchings in Sparse Random Graphs
IEEE Annual Symposium on Foundations of Computer Science · 1981
233
cited
Borel sets and circuit complexity
Symposium on the Theory of Computing · 1983
219
cited
GO Is Polynomial-Space Hard
JACM · 1980
188
cited
The history and status of the P versus NP question
Symposium on the Theory of Computing · 1992
182
cited
Maximum matching in sparse random graphs
22nd Annual Symposium on Foundations of Computer Science (sfcs 1981) · 1981
180
cited
Nondeterminism and the size of two way finite automata
Symposium on the Theory of Computing · 1978
173
cited
Limit on the Speed of Quantum Computation in Determining Parity
1998
161
cited
Expanders, Randomness, or Time versus Space
Journal of computer and system sciences (Print) · 1988
146
cited
On the power of multi-power interactive protocols
[1988] Proceedings. Structure in Complexity Theory Third Annual Conference · 1988
124
cited
Halting space-bounded computations
19th Annual Symposium on Foundations of Computer Science (sfcs 1978) · 1978
119
cited
Compression and ranking
Symposium on the Theory of Computing · 1985
116
cited
On Completeness and Soundness in Interactive Proof Systems
Advances in Computational Research · 1989
110
cited
Sotabase