John E. Savage An Wang Professor of Computer Science

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, reliable computation with unreliable components, and cybersecurity. He is a Fellow of AAAS and ACM, a Life Fellow of IEEE, and a Guggenheim Fellow. He served as a Jefferson Science Fellow during the 2010 academic year in the US State Department.

Professor Savage has been heavily involved in departmental, faculty and university affairs. His recent assignments include Chair and Member of the Nominations Committee (2010-2013), Chair of the Faculty (2001-2002), Faculty Officer (2000-2003), 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). He is a recipient of the President's Award for Excellence in Faculty Governance.

Brown Affiliations

Research Areas

scholarly work

View My Full Publication List Here

research overview

A recurring theme in Prof. Savage's work is the development of fundamental limits on computation, a theme that emerged in his 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 more recent research includes computational nanotechnology and coded computation. His current focus is on cybersecurity policy and technology.

research statement

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, the first textbook on circuit complexity. It made evident the importance of circuit complexity to theoretical computer science. He co-authored a computer literacy textbook 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 and multi-core computation are recent areas of interest. Cybersecurity policy and technology are new research interests that emerged from his year in the U.S. Department of State as a Jefferson Science Fellow, 2009-2010.

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