Richard Edwin Stearns Ph.D., Princeton University Distinguished Professor Emeritus res@cs.albany.edu  (Personal Page) Computer Science Department University at Albany Albany, NY 12222 (518) 442-4270 (Department Office) (518) 442-5638 (FAX)

Turing Award Citation - 1993 To Juris Hartmanis and Richard E. Stearns, in recognition of their seminal joint research which established the foundations for the field of computational complexity theory. In their paper "On the Computational Complexity of Algorithms," (Transactions of the American Mathematical Society, vol. 117, No. 5, May, 1965, pp. 285-306) they provided a precise definition of the complexity measure defined by computation time on Turing machines and developed a theory of complexity classes. The paper sparked the imagination of many computer scientists and led to the establishment of complexity theory as a fundamental part of the discipline.

Personal Statement of Research

Stated in general terms, my research interests include computational complexity, automata theory, analysis of algorithms, and game theory. We are currently studying the circumstances in which certain instances of hard problems are easier to solve than the general problems. In particular, we have found it useful to describe computational problems algebraically. These descriptions allow us to attribute structure to problem instances and to develop genetic algorithms which solve structured problem instances much faster than brute force methods. We are using these techniques to study approximation algorithms and are extending them to cover succinct representations.

Books

Hartmanis, J. and Stearns, R.E., Algebraic Structure Theory of Sequential Machines, Prentice-Hall, 1966.

Lewis, P.M., Rosenkrantz, D.J. and Stearns, R.E., Compiler Design Theory, Addison Wesley Publishing Co., 1976.

Aumann, Robert J. and Maschler, Michael B. with the collaboration of Stearns, Richard E., Repeated Games with Incomplete Information, MIT Press, 1995. This book won the 1995 Lanchester Prize for the best contribution of the year to Operations Research.

Selected Publications

Hartmanis, J. and Stearns, R.E., On the Computational Complexity of Algorithms, Trans. Am. Math. Soc., vol. 117, #5, May 1965, 285-306.

Lewis, P.M. and Stearns, R.E., Syntax-Directed Transduction, Journal of ACM, 15, July 1968, pp. 465-488.

Stearns, R.E., Convergent Transfer Schemes for N-Person Games, Trans. Am. Math. Soc., 134, December 1968, pp. 449-459.

Rosenkrantz, D.J., Stearns, R.E. and Lewis, P.M., An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal on Computing, 6, September 1977, pp. 563-581.

Rosenkrantz, D.J., Stearns, R.E. and Lewis, P.M., Consistency and Serializability in Concurrent Database Systems, SIAM Journal on Computing, 13, August 1984, pp. 508-530.

Stearns, R.E. and Hunt III, H.B., Power Indices and Easier NP-complete Problems, Mathematical Systems Theory, 23, 1990, pp. 209-225.

Stearns, Richard Edwin, It's Time to Reconsider Time, Communications of the ACM, 37, November 1994, pp. 95-99.

Stearns, R.E. and Hunt III, H.B., An Algebraic Model for Combinatorial Problems, SIAM Journal on Computing, 25, April 1996, pp. 448-476.

Stearns, R.E. and Hunt III, H.B.,Exploiting Structure in Quantified Formulas, Journal of Algorithms, 43, 2002, pp. 220-263.