Juris Hartmanis
Walter R. Read Professor of Engineering
PhD 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 is the study of the quantitative laws that govern computation, and it is an essential part of the science base needed to guide, harness, and exploit the explosively growing computer technology. 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 in problem solving, with particular attention to sequential-time, parallel-time, nondeterministic-time, memory requirements, randomness as a computational resource, and interactive computing.

University Activities

• Member, Faculty Council of Representatives
• Chair, Computer Science Department Recruiting Committee

Honors

• ACM Turing Award (with R.E.Stearns)
• Member, National Academy of Engineering
• Foreign Member, Latvian Academy of Sciences
• Fellow, American Academy of Arts and Sciences
• Fellow, New York State Academy of Sciences
• Fellow, American Association for the Advancement of Science (AAAS)
• Charter Fellow of the ACM

Professional Activities

• Editor: Springer-Verlag Lecture Notes in Computer Science,SIAM Journal of Computing, Journal of Computer and Systems Sciences
• Advisory Board for EATCS Monographs in Theoretical Computer Science, Springer-Verlag
• Board of Directors, Computing Research Association, 1989-1994
• IFIP Technical Committee for Foundations of Computer Science
• Advisory Council, George P. Brown School of Engineering, Rice University, Houston, Texas
• National Academy of Engineering Peer Committee for Computer Science and Engineering, 1991-1994
• Visiting Committee to the Physical Sciences Division, University of Chicago, 1992-1995
• EATCS Council, 1991-
• Board of Advisors: International Journal for the Foundations of Computer Science, World Scientific Press
• 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
• Goedel Prize Committee
• Member, Computer Science and Telecommunications Board of the National Research Council,1995-98

Awards

• Honorary doctoral degree, Dr.h.c., University of Dortmund, Germany,1995

Lectures

• Some observations about computer science. Banquet speech, International Logic Programming Symposium, Cornell University, November 16,1994.
• Computational complexity: its scope, nature and future. Distinguished Lecture Series, University of Virginia, February 13, 1995.
• ___. Distinguished Lecture Series, University of Tennessee, April 17, 1995.

Publications

• On computational complexity and the nature of computer science. Turing Award Lecture. Communications of the ACM 37,10, (October 1994), 37-43.
• The random Oracle hypothesis is false. Journal of Computer and System Sciences 49, 1, (August 1994), 24-39 (with Richard Chang, Benny Chor, Oded Goldreich, Johan Hastad, Desh Ranjan, and Pankaj Rohatgi).
• On Hausdorff and topological dimension of the Kolmogorov Complexity of the real line. Journal of Computer and System Sciences 49, 3, (December 1994), 605-619 (with Jin-yi Cai).
• On the weight of computations. EATCS Bulletin 55, (February 1995), 136-138.

1994-1995 Annual Report Home Page

Departmental Home Page

If you have questions or comments please contact: www@cs.cornell.edu.

---

Last modified: 24 November 1995 by Denise Moore (denise@cs.cornell.edu).