 |
John E. Savage
Professor of Computer ScienceContact Information
Box 1910Brown University
Providence, RI 02912
Email: jes at cs.brown.edu
Personal home page: http://www.cs.brown.edu/~jes/
Research Areas
| Nanocomputing |
| Design and Analysis of Algorithms |
| Parallel Computing |
| Theory of Computation |
Research Topics or Projects
| Nanoelectronic Computing |
| PARED - Parallel Adaptive Unstructured Computation |
| The Design and Analysis of Dynamic Processes: A Stochastic Approach |
Courses Taught
Research 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.
Selected Publications
Rachlin, E., and Savage, J. E. Nanowire Addressing with Randomized-Contact Decoders. Theoretical Computer Science 406 (Nov. 2008). [ pdf ]
Savage, J., and Zubair, M. A Unified Model for Multicore Architectures. In 1st International Forum on Next-Generation Multicore/Manycore Technologies (Cairo, Egypt, Nov. 2008).
Rachlin, E., and Savage, J. E. A Framework for Coded Computation. In Proceedings of IEEE Intl. Symp. on Information Theory (July 2008), IEEE, pp. 2342-2346. [ pdf ]
Rachlin, E., and Savage, J. E. Analysis of Mask-Based Nanowire Decoders. IEEE Trans. Computers 57, 2 (Feb. 2008), 175-187. [ pdf ]
Rachlin, E., and Savage, J. E. Addressing in the Face of Uncertainty. In Proceedings of the International Symposium on Very Large-Scale Integration (VLSI) (Feb. 2006), IEEE Computer Society, pp. 225-230. [ pdf ]
Savage, J. E., Rachlin, E., DeHon, A., Lieber, C. M., and Wu, Y. Radial Addressing of Nanowires. ACM Journal on Emerging Technologies in Computing Systems 2, 2 (2006), 129-154. [ pdf ]
Gojman, B., Rachlin, E., and Savage, J. E. Evaluation of Design Strategies for Stochastically Assembled Nanoarray Memories. ACM Journal on Emerging Technologies in Computing Systems 1, 2 (July 2005), 73-108. [ pdf ]
Gottlieb, L.-A., Savage, J. E., and Yerukhimovich, A. Efficient Data Storage in Large Nanoarrays. Theory of Computing Systems 38, 4 (July 2005), 503-536. [ pdf ]
DeHon, A., Lincoln, P., and Savage, J. E. Stochastic Assembly of Sublithographic Nanoscale Interfaces. IEEE Transactions on Nanotechnology 2, 3 (Sept. 2003), 165-174. [ pdf ]
Castaños, J. G., and Savage, J. E. PARED: A Framework for the Adaptive Solution of PDEs. In Procs. Eighth IEEE Int. Symp. High Performance Distributed Computing (HPDC'99) (Mar. 1999), p. 15. [ pdf ]
All publications by John E. Savage
| Page Owner: John E. Savage | Last Modified: Fri Jan 23 12:17:14 2009 |