Computation theory talk by David Doty, Mon 11 June

[Pekka Orponen]

ICS Forum talk:

Deterministic Computation with Chemical Reaction Networks

Dr. David Doty
California Institute of Technology, USA

Abstract:

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) =3D 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

About the speaker:

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.

Date: Monday, 11 June, 2012
Time: 13:15--14:00
Venue: Lecture hall T2, Computer Science building

Welcome!

Further information: <http://ics.tkk.fi/en/current/ics_forum/>