Speaker: Juris Hartmanis Cornell University, USA
Time: 2007-09-20 09:00-2007-09-20 10:00
Venue: FIT Building Lecture Hall, Tsinghua University
Download: Click!

Abstract:

This talk will review the classic separation problems of Computational Complexity classes and mention some possible approaches. It will also discuss the impact of the Internet and some results and problems about networks.

Short Bio:

Professor Juris Hartmanis has been a leader in the field of Theoretical Computer Science for the past 40 years. Together with Dick Stearns, he wrote one of the earliest papers in the field "On the computational complexity of algorithms" (Trans. Amer. Math. Soc., 177 (1965), 285-306) in which they first proposed the fundamental idea of capturing the quantitative behavior of computation, and to classify computations by their intrinsic computational complexity. Their papers firmly established computational complexity theory as a mathematical discipline. It is with this paper the field took its name.
        Hartmanis and Stearns shared the ACM A. M. Turing Award in 1993, "In recognition of their seminal paper which established the foundations for the field of computational complexity theory." To quote Dick Karp, another Turing Award winner, "it is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of complexity theory. Using the Turing machine as their model of an abstract computer, Hartmanis and Stearns provided a precise definition of the complexity class consisting of all problems solvable in a number of steps bounded by some given function of the input length n,… All of us who read their paper could not fail to realize that we now had a satisfactory formal framework for pursuing the questions that Edmonds had raised earlier in an intuitive fashion—questions about whether, for instance, the traveling salesman problem is solvable in polynomial time." The latter problem, after the work of Cook and Karp, is now universally known as the P versus NP problem.
        Professor Hartmanis has also been a founder of a leading center of computer science research at Cornell University. He established one of the very first Department of Computer Science in the world, and served as its first Chairman. Under his guidance, Cornell's Computer Science Department became a top research department, which has always been ranked among the top departments in the US.
        At the national level, Prof. Hartmanis was very influential in shaping the direction of Computer Science research in the US. For several years he served as the leading person at the US National Science Foundation responsible for all Computer Science research funded by the US National Science Foundation. In that capacity, Juris was responsible for a major study "Computing the future: a broader agenda for computer science and engineering" by the National Research Council, coauthored with Herbert Lin, which sets out the new direction of Computer Science research in the next decade.
        Juris is nominated as Einstein Professor of the Chinese Academy of Sciences in 2006.