Current nanoscale fabrication allows creating dense circuits, e.g., nanowire crossbars with spacings of about 10nm . With active molecular components between the crossed nanowires, these structures could form dense memory and logic circuits .
Unfortunately, current technology cannot reliably connect large numbers of nanoscale devices into precisely specified circuits. While lithography can create microscale circuits with many components, high yield and low unit cost, this combination of capabilities is not yet possible for molecular-scale devices.
Thus one practical challenge for dense nanoscale circuits is fabricating interfaces to provide input data and extract the results. Such interfaces must connect nanoscale circuits with the far larger microscale electronics, but current technology cannot form precisely patterned connections at the density required for the nanoscale circuits.
An alternate approach to fabricating interface circuits relies on self-assembly: forming connections via a stochastic process, resulting in random variation in the final circuit. Thus designing a circuit for fabrication via self-assembly must account for this variation. Fortunately, various statistical regularities allow reliable circuit construction in spite of random variations [3,4].
As a specific example, we examine the design of a demultiplexer useful for addressing dense nanoscale circuits via a small number of larger wires fabricated with conventional lithography . Ideally, such circuits allow selecting one of N individual wires with an address specified by only of order log(N) addressing wires. We show how this advantage remains in spite of random variation in the connections due to self-assembly. Specifically, adding a few more addressing wires than would be required when there is no variation makes the resulting circuit very likely to be able to address all the nanowires. For circuits consisting of many nanowires, the probability of fabricating a functional demultiplexer shows an abrupt transition to near perfect performance as the number of additional wires increases. This threshold, which provides a design guideline for constructing such circuits, is analogous to the well-known behavior of the likelihood two people in a group share the same birthday as the size of the group increases.
More generally, the existence of these statistical thresholds provides opportunities to reliably create other dense nanoscale circuits in spite of random variations introduced during fabrication. An important open issue for extending this work is better understanding of the stochastic nature of various self-assembly processes, such as the extent to which defect locations are correlated.
 N. Melosh et al., Ultrahigh-Density Nanowire Lattices and Circuits, Science 300:112-115 (2003)
 C. P. Collier et al., Electronically Configurable Molecular-Based Logic Gates, Science 285:391-394 (1999)
 J. von Neumann, Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components, Automata Studies 34:43-98 (1956)
 J. Heath et al., A Defect-Tolerant Computer Architecture: Opportunities for Nanotechnology, Science 280:1716-1721 (1998)
 P. J. Kuekes and R. S. Williams, Demultiplexer for a Molecular Wire Crossbar Network, US Patent 6,256,767, 2001