Juris Hartmanis

Juris Hartmanis
Walter R. Read Professor of Engineering
Turing Award Winner
jh@cs.cornell.edu
http://www.cs.cornell.edu/Info/ Annual96/Faculty/jh.html
Ph.D. California Institute of Technology, 1955

The strategic goal of our research is to contribute to the development of a comprehensive theory of computational complexity. Computational complexity, the study of the quantitative laws that govern computation, is an essential part of the science base needed to guide, harness, and exploit the explosively growing computer technology.

Our research has two main goals: a) to understand better what makes problems hard to compute and to develop techniques to verify the degree of hardness, and b) to explore what is the best that can be done with computational resources that are not sufficient to solve a problem.

Computational complexity classifies problems by the amounts of various computational resources needed to solve them. This classification yields complexity classes, each of which consists of all problems that can be solved within a given computational resource bound. To gain a deeper understanding of what makes problems hard to compute, we explore various complexity classes, relations between these classes, and the internal structure of these classes. We also study the trade-offs between different computational resources, with particular attention to sequential-time, parallel-time, nondeterministic-time, memory requirements, randomness as a computational resource, and interactive computing.

Awards

Dr. h.c., University of Dortmund, Germany, 1995
Bolzano Gold Medal of the Academy of Sciences, Czech Republic, 1995

University Activities

Acting Chair: Computer Science Department, Fall 1995
Member: Executive Committee of the Faculty Council of Representatives
Chair: Computer Science Recruiting Committee

Professional Activities

Member: National Academy of Engineering
Foreign Member: Latvian Academy of Sciences
Fellow: American Academy of Arts and Sciences; New York State Academy of Sciences; American Association for the Advancement of Science (AAAS)
Member: National Research Council Computer Science and Telecommunications Board; Turing Award Committee; Goedel Prize Committee; Waterman Award Committee; Visiting Committee to the Physical Sciences Division, University of Chicago, 1992-1998; Program Committee for COCOON '96
Editor: Springer-Verlag Lecture Notes in Computer Science; SIAM Journal on Computing; Journal of Computer and Systems Sciences
Advisory Board: EATCS Monographs in Theoretical Computer Science, Springer-Verlag
IFIP Technical Committee for Foundations of Computer Science
Board of Advisors: International Journal for the Foundations of Computer Science; World Scientific
Editorial Board: Chicago Journal of Theoretical Computer Science; Electronic Journal for the Foundation of Computer Science; MIT Press
Foundations Editor: Electronic Journal for Universal Computer Science.

Lectures

The computing paradigm and computational complexity. Distinguished Lecture Series, University of Pittsburgh, March 15, 1996.
____. 13th Maryland Theoretical Computer Science Day. Computer Science, University of Maryland, October 6, 1995.
____. Computer Science, University of Dort-mund, Dortmund, Germany, July 7, 1995.
Separation problems in computational complexity. Max Planck Institute, Saarbruecken, Germany, July 5, 1995.

Publications

On the computing paradigm and computational complexity. Mathematical Foundations of Computer Science. August - September, 1995. Prague. J. Wiedermann and P. Hajek, eds. LNCS 969, Springer-Verlag, 82-02.
Turing Award Lecture: On the computational complexity and the nature of computer science. ACM Computing Surveys 27, 1 (March 1995), 7-16. (Reprinted from Communications of the ACM 37,10 (1994) as part of Computing Surveys Symposium on Computational Complexity and the Nature of Computer Science, (March 1995.)

Return to: