Nicholas Schiefer: Models of distributed computing in molecular programming

Tuesday, November 22, 2016 - 2:00pm to 3:30pm
Nicholas Schiefer

Molecular programming is the study of computation with "molecules", which are extremely simple computational agents that interact with each other through relatively simple, predefined rules to perform computation. From an engineering perspective, they provide a formal background to ongoing research in nanotechnology. From a scientific perspective, they provide some kind of insight about the mechanisms that effect computation in real-world chemical systems. From the perspective of distributed computing, they provide a kind of "maximally distributed" setting for studying computation.

I will give an introduction to chemical reaction networks (CRNs, which are equivalent to population protocols) and Winfree's abstract tile assembly model (aTAM), and discuss major theoretical results and extensions. Along the way I will mention major experimental results about the implementation of molecular programs. Time permitting, I will discuss some recent joint work with Erik Winfree on a model that combines CRNs and the aTAM.