 |
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. In Procs. IEEE/ACM Int. Conf. on Computer-Aided Design (ICCAD) (Nov 2006). [ 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 ]
Rachlin, E., Savage, J. E., and Gojman, B. Analysis of a Mask-Based Decoder. In Procs. Annual Symposium on VLSI (May 2005), IEEE Computer Society, pp. 6-13. [ 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 (Jul 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 (Jul 2005), 503-536. [ pdf ]
DeHon, A., Lincoln, P., and Savage, J. E. Stochastic Assembly of Sublithographic Nanoscale Interfaces. IEEE Transactions on Nanotechnology 2, 3 (Sep 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 ]
Fischer, P. F., Preparata, F. P., and Savage, J. E. Generalized scans and tri-diagonal systems. In Procs. Symposium on Theoretical Aspects of Computer Science (1995), pp. 168-180. [ pdf ]
Savage, J. E., and Wloka, M. G. Parallelism in Graph Partitioning. Journal of Parallel and Distributed Computing 13, 3 (Nov 1991), 257-272. [ pdf ]
Savage, J. E. The Performance of Multilective VLSI Algorithms. Journal of Computer and Systems Sciences 29, 2 (Oct 1984), 243-273.
Savage, J. E. Area-Time Tradeoffs for Matrix Multiplication and Related Problems in VLSI Models. Journal of Computer and Systems Sciences 22, 2 (Apr 1981), 230-242.
Savage, J. E. Computational Work and Time on Finite Machines. Journal ACM 19, 4 (Oct 1972), 660-674. [ pdf ]
All publications by John E. Savage
| Page Owner: John E. Savage | Last Modified: Mon Aug 20 14:30:39 2007 |