Juris Hartmanis

Walter R. Read Professor of Engineering
Chairperson, Department of Computer Science
Ph.D., California Institute of Technology, 1955

Research Interests

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. Our research has two main goals:

  • to understand better what makes problems hard to compute and to develop techniques to verify the degree of hardness, and

  • to explore what is the best that can be done with computational resources 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 that consist 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.

    Selected Publications

  • Cai, J., T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The Boolean hierarchy II: Applications. SIAM Journal of Computing, vol. 18, 1989, 95-111.

  • Hartmanis, J., R. Chang, D. Ranjan and P. Rohatgi. Structural complexity theory: Recent surprises. Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, Springer-Verlag Lecture Notes in Computer Science, vol. 447, 1990, 1-12.

  • Hartmanis, J., R. Chang, D. Ranjan and P. Rohatgi. On IP = PSPACE and theorems with narrow proofs. Bulletin of the European Association for Theoretical Computer Science, vol. 41, 1990, 166-174.

  • Ranjan, D., R. Chang and J. Hartmanis. Space bounded computations: Review and new separation results. Theoretical Computer Science, vol. 80, 2, 1991, 289-302.

  • J. Hartmanis and H. Lin. Computing the Future: A Broader Agenda for Computer Science and Engineering. National Academy Press. Washington, D.C. 1922 Report of National Research Council Study, chaired by J . Hartmanis.

  • J. Hartmanis. Strucural Complexity Column: A Broader Adjenda for Theory. EATCS Bulletin, vol. 49, 1993, 125-129.