Molecular Computing and Probabilistic Circuits


Jehoshua (Shuki) Bruck



Why does the functioning of biological systems seem miraculous? One reason is that we do not know how to design systems that do what cells do, namely molecular computing. In contrast, we know how to design highly complex information systems. The fundamental reason for the successful evolution of information systems is the development of mathematical abstractions that enable efficient and robust design processes. In particular, Claude Shannon in his classical 1938 Masterís Thesis demonstrated that all Boolean functions can be computed by relay circuits, leading to the development of digital logic and resulting in computer chips with over a billion transistors. Motivated by the challenge of analyzing stochastic gene regulatory networks, we generalize the notion of logic design to probabilistic logic design. Specifically, we consider relay circuits where deterministic switches are replaced by probabilistic switches. We present efficient algorithms for synthesizing probabilistic relay circuits that can compute arbitrary probability distributions.