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.
- Member, Faculty Council of Representatives
- Chair, Computer Science Department Recruiting Committee
- 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
- 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,
- 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
- 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
- Honorary doctoral degree, Dr.h.c., University of Dortmund, Germany,1995
- 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.
- 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:
Last modified: 24 November 1995 by Denise Moore