John Savage
Professor:
Computer Science
Phone: +1 401 863 7642
Phone 2: +1 401 863 7600
John_Savage@Brown.EDU
A recurring theme in Prof. Savage's work is the development of fundamental limits on computation, a theme that emerged in the study of the complexity of decoders for error correcting codes. His interests also include the design and analysis of algorithms, which has been expressed in several areas including serial and parallel computer aided design, and distributed computing for scientific computation. His current research focus is computational nanotechnology and coded computation.
Biography
Professor Savage earned his PhD in Electrical Engineering at MIT in 1965 specializing in coding and information theory. He joined Bell Laboratories in 1965 and the faculty of the Division of Engineering at Brown in 1967. In 1979 he co-founded the Department of Computer Science and served as its second chair from 1985 to 1991. By the early 1970s his research interests changed to theoretical computer science. His current research focus is computational nanotechnology. He is a Fellow of AAAS and ACM, a Life Fellow of IEEE, and a Guggenheim Fellow.
Professor Savage has been heavily involved in departmental, faculty and university affairs. His recent assignments include Chair of the Faculty (2001-2002), Chair of the Task Force on Faculty Governance (2002-2003) that revised the faculty committee structure in one year, member of the Academic Priorities Committee (2002-2003), Chair of the Search Committee for the Vice President for Public Affairs and University Relations (2003-2004), and President of the Faculty Club Board of Managers (1998-2001).
Interests
John Savage began his research career as a coding and information theorist within electrical engineering. The empirical observation that decoders for error-correcting codes are much more complex than encoders propelled him to investigate the complexity of decoders. This naturally led to a study of tradeoffs between computational resources and the study of circuit complexity, a fundamental computational measure in terms of which tradeoffs can be expressed. Much of this early work was captured in his 1976 book, The Complexity of Computing, which made evident the importance of circuit complexity to theoretical computer science. He co-authored a textbook for a computer literacy course with two undergraduates in the mid-1980s and in 1998 authored Models of Computation, a nearly comprehensive introduction to theoretical computer science.
A recurring theme in Prof. Savage's work is the development of fundamental limits on computation, a theme that emerged in the study of decoder complexity. It has been expressed in the development of lower bounds, whether they be on a single resource, such as circuit size or depth, or expressed as tradeoffs between computational resources, such as space and time in serial computation, area and time in VLSI computation, or primary storage capacity and I/O operations in I/O-limited computations. It has also been seen in the classification of problems by their membership in traditional complexity classes, such as P, NP, and BPP. Another recurring theme has been the design and analysis of algorithms, which has been expressed in several areas including serial and parallel computer-aided design, distributed computing for scientific computation, and his recent work on computational nanotechnology. The challenge of the latter area is to produce deterministic computing elements when the assembly process is stochastic and unpredictable. Computer architecture, probability theory, and complexity analysis play important roles here. Computing with unreliable elements is a new area of interest.
Degrees
BSc, MSc, PhD
Awards
Fellow, American Association for the Advancement of Science (AAAS), 1997
Fellow, Association of Computing Machinery (ACM), 1996
Fellow, Institute of Electrical and Electronics Engineers (IEEE), 1992
Guggenheim Fellowship 1973-1974
Fulbright-Hays Research Award, 1973-1974
National Science Foundation Cooperative Graduate Fellow, 1961-1962
Affiliations
Fellow, American Association for the Advancement of Science (AAAS), 1997
Institute of Electrical and Electronics Engineers (IEEE) Golden Core Member, 1996
Fellow, Association of Computing Machinery (ACM), 1996
Fellow, IEEE, 1992
Senior Member, IEEE, 1991
Member, Sigma Xi, 1961
Member, Eta Kappa Nu, 1960
Member, Tau Beta Pi, 1960
Teaching
My teaching is primarily in the area of theory of computation but has included analysis of algorithms, introduction to scientific programming, operating systems, computer architecture, information theory and communication theory.
Funded Research
NIRT: Technologies, Architectures and Performance Analysis for Nanoelectronics (supplement) (PI), National Science Foundation, $19,995, 2005
NIRT: Technologies, Architectures and Performance Analysis for Nanoelectronics (PI), National Science Foundation, $1,300,000, 2004 - 2008
NER: Exploring the Computational Limits Imposed by Nanotechnologies (PI), National Science Foundation, $97,828, 2002 - 2003
Acquisition of a Parallel Supercomputer (Co-PI), National Science Foundation, $300,000, 1994-1996
Investigations in Programmable Systolic Architectures (PI), National Science Foundation, $180,882, 1991-1995
High-Performance Design Environments (PI), Defense Advanced Research Projects Agency (DARPA)/Office of Naval Research, $2,580,000, 1991-1996
Multiparadigm Design Environments (Co-PI), National Science Foundation, $3,504,831, 1988-1993
Multiparadigm Design Environments (PI), Defense Advanced Research Projects Agency (DARPA)-Office of Naval Research (ONR), $1,776,120, 1987 - 1990
Hierarchial Silicon Compilation (PI), Semiconductor Research Corporation, $158,733, 1986 - 1988
VLSI (Very Large Scale Integrated) Algorithms and Analysis (PI), National Science Foundation, $238,932, 11/1983 - 10/1988
Hierarchial Silicon Compilation (PI), Semiconductor Research Corporation, $306,997, 1983-1986
Ideographics (PI), Defense Advanced Research Projects Agency (DARPA)-Office of Naval Research (ONR), $1,700,000, 1983 - 1987
An Integrated Experimental Environment for Research in Computer Science (Co-PI), National Science Foundation, $2,736,377, 1982-1987
Applied Computational Complexity (PI), National Science Foundation, $106,021, 6/1/1981 - 12/31/1983
Analysis of Algorithms and Data Structures (PI), National Science Foundation, $133,352, 1976 - 1981
Analysis of Decoder Complexity (PI), National Science Foundation, $71,157, 1975 - 1980
A Study of Algorithms and Data Structures (PI), National Science Foundation, $74,000, 1974 - 1976
The Performance of Computing Systems and Compiler Analysis (PI), National Science Foundation, $57,700, 1972 - 1975
Analysis of Algorithms and Machines (PI), Defense Advanced Research Projects Agency (DARPA), $50,000, 1972 - 1975
Code Parameters and Decoder Complexity (PI), NASA, $24,900, 6/1/1970 - 5/31/1971
Decoders for Error Correction (PI), National Science Foundation, $34,500, 9/1/1969-8/31/1971
A Study of Decoders for Error Correction (PI), NASA, $28,000, 6/1/1969 - 5/31/1970
A Study of the Power and Complexity of Decoding Machines (PI), National Science Foundation, $15,000, 1968-1969
