Probabilisitic Models for Nanoscale Computation

John E. Savage
Computer Science
Brown University


Advances have been been made recently in assembling nanoscale devices using
non-photolithographic means. This important development, which offers the potential for
greatly increasing the density of memory cells and logic gates, introduces a new model of
computation and new analytical challenges.  In this talk we provide an introduction to this
new development.

The difficulty of assembling irregularly placed nanoscale devices has caused the research
community to focus on regular arrays of such devices and, in particular, the crossbar. All
known methods for controlling individual nanowires (NWs)in a crossbar by mesoscale wires
(MWs) introduces randomness in the connections. This presents several questions. First, which
methods of controlling NWs with MWs devotes the smallest amount of area for this purpose?
Second, how can stochastically assembled chips be configured after assembly? Third, since
errors will occur during assembly, how can chips be designed to minimize the effect of such
errors? Finally, what computational limitations do stochastically assembled, crossbar-based
computers introduce? We will address these and other questions. 


Biography:

John Savage is Professor of Computer Science at Brown University. He earned his PhD in
Electrical Engineering at MIT in 1965 and his bachelor's and Master's degrees, also at MIT,
in 1962. He was employed by Bell Laboratories from 1965 until 1967 when he joined the faculty
at Brown university. He is a founder of the Department of Computer Science and was its chair
from 1985 to 1991. 

Savage's early research was in information theory and communication theory. His work on the
complexity of decoders for error correcting codes in the 1960s led him into theoretical
computer science and to the introduction of circuit complexity into the field. His first
book, The Complexity of Computing, published in 1976, became the standard reference on
circuits. He has also contributed to research on space-time tradeoffs, area-time tradeoffs in
VLSI, I/O time-space tradeoffs, silicon compilers, and parallel algorithms for VLSI and the
finite-element method. His current research focus is computational nanotechnology. He is a
Fellow of AAAS and ACM, a Life Fellow of IEEE, and a Guggenheim Fellow.