Richard E. Stearns
# Richard E. Stearns

Richard Edwin „Dick“ Stearns (* 5. Juli 1936 in Caldwell, New Jersey) ist ein US-amerikanischer Informatiker, der 1993 gemeinsam mit Juris Hartmanis den Turing Award für seine Leistungen auf dem Gebiet der Komplexitätstheorie erhielt.

## Leben

Stearns erlangte den Bachelor im Fach Mathematik 1958 am Carleton College, 1961 promovierte er in Mathematik bei Harold W. Kuhn an der Princeton University zum spieltheoretischen Thema Three Person Cooperative Games Without Side Payments.

Schon zuvor, im Sommer 1960, hatte er in der Forschungsabteilung von General Electric in Schenectady mit Juris Hartmanis gearbeitet. Diese Tätigkeit setzte er im Juni 1961 fort. 1964 veröffentlichten er und Hartmanis das für die Komplexitätstheorie wegweisende und namensgebende Paper Computational complexity of recursive sequences (1965 als On the computational complexity of algorithms wiederveröffentlicht), in dem sie unter anderem DTIME und damit generell Komplexitätsklassen sowie ein frühes Speedup-Theorem einführten. Zusammen mit Phil Lewis führten Stearns und Hartmanis 1965 neben der Zeit- auch die Platzkomplexität ein. Erst nach diesen Arbeiten kam Stearns erstmals mit Computern in Berührung.

Ab September 1978 war Stearns an der University at Albany, wo er von Januar 1982 bis August 1989 die Fakultät für Informatik leitete. Im Jahr 1994 wurde er als Distinguished Professor geehrt, seit September 2000 ist er emeritiert.

1975 war er Gastprofessor an der Hebräischen Universität Jerusalem, von 1977 bis 1978 außerplanmäßiger Professor am Rensselaer Polytechnic Institute, und 1985 Gastwissenschaftler am Mathematical Sciences Research Institute der University of California, Berkeley.

Stearns ist verheiratet und hat zwei Kinder.

Er war Gründungsmitglied der Game Theory Society und ist Fellow der ACM.

## Preise und Ehrungen

* 1995: Frederick-W.-Lanchester-Preis (mit Robert Aumann und Michael Maschler)

## Schriften

* mit Juris Hartmanis: On the computational complexity of algorithms. In: Transactions of the American Mathematical Society. Vol. 117, 1965, S. 285–306. Zunächst als Computational complexity of recursive sequences. In: Proceedings of the Fifth Annual IEEE Symposium on Switching Circuit Theory and Logical Design Princeton (N.J.) 1964, S. 82–90.
* mit Juris Hartmanis & Phil M. Lewis: Hierarchies of Memory Limited Computations. In: Proceedings of the Sixth Annual IEEE Symposium on Switching Circuit Theory and Logical Design. Ann Arbor (Mich.) 1965, S. 179–190 (PDF; 398 kB).
* mit Frederick C. Hennie: Two-tape simulation of multi-tape turing machines. In: Journal of the ACM. Vol. 13, No. 10, Oktober 1966, S. 533–546.
* mit Harry B. Hunt: Power indices and easier hard problems. In: Mathematical Systems Theory. Vol. 23, 1990, S. 209–225 (PDF; 475 kB).
* It’s Time to Reconsider Time. In: Communications of the ACM. Vol. 37, No. 11, November 1994, S. 95–99 (PDF; 754 kB).
* mit Robert Aumann & Michael Maschler: Repeated Games with Incomplete Information. MIT Press, 1995
