Department of Information and Computer Science

11.06.2012 / 13:15 - 14:00

Location: Lecture hall T2, Computer Science Building, Konemiehentie 2, 02150, Espoo, FI

Dr. David Doty, California Institute of Technology, USA

We study the deterministic computation of functions on tuples of natural numbers by chemical reaction networks (CRNs). CRNs have been shown to be efficiently Turing-universal when allowing for a small probability of error. CRNs that are guaranteed to converge on a correct answer, on the other hand, have been shown to decide only the semilinear predicates.

We introduce the notion of function, rather than predicate, computation by representing the output of a function f:N^k --> N^l by a count of some molecular species, i.e., if the CRN starts with n_1,...,n_k molecules of some "input" species X_1,...,X_k, the CRN is guaranteed to converge to having f(n_1,...,n_k) molecules of the "output" species Y_1,...,Y_l. We show that a function f:N^k --> N^l is deterministically computed by a CRN if and only if its graph { (x,y) \in N^k x N^l | f(x) = y } is a semilinear set.

We show that each semilinear function f can be computed on input x in expected time O(polylog |x|).

We also discuss some preliminary results on lower bounds for time complexity of computation by deterministic CRNs using a combinatorial "adversarial" model of time complexity and state some conjectures regarding time lower bounds for tasks such as leader election in the original stochastic time complexity model.

Joint work with Ho-Lin Chen and David Soloveichik

* David Doty received his PhD from Iowa State University in 2009. Currently he is a postdoctoral researcher at California Institute of Technology (Caltech), and a receiver of the Computing Innovation Fellowship. His research interest include (among other) theory of nanoscale algorithmic self-assembly, biomolecular computations, algorithmic information theory, and computational complexity. *

If you are interested to discuss with the speaker, please contact his host, Dr. Eugen Czeizler (eugen.czeizler@aalto.fi).

Map © OpenStreetMap. Some rights reserved.