From: David Kempe (kempe@cs.washington.edu)
Date: Tue Apr 27 2004 - 16:39:47 PDT
Dear theory lovers,
Next theory seminar:
Title: An Introduction to Combinatorial Self-Assembly, Part 1
Time: Friday, 4/29, 11:30am-12:20pm
Place: wherever it usually is
Guide: David Kempe
Abstract:
Self-assembly is the process by which small simple objects (called
"tiles"), exposed to the right physical conditions, assemble into a
larger, complex, and desirable aggregate object. It has been suggested
that self-assembly may become an important technology for circuit
design and nano-fabrication. For instance, a memory chip consists of
many identical gates arranged in regular patterns, and one could
imagine designing identical gates in such a way that billions of them
will arrange into a working memory chip (with the help of a few more
other gates, of course).
On the experimental side, there has recently been progress on
self-assembling larger objects from DNA-based tiles. Along with the
experimental progress, the theory of self-assembly is now receiving
more attention, including questions such as:
- What are good mathematical models, and how do choices in those
models affect the computational complexity of problems?
- How powerful is self-assembly as a computational model?
- How many different types of tiles or glue between them are needed to
assemble the object I want?
- How long will the assembly process take?
- How to deal with the inevitable errors that happen in practice, and
how to reduce the number of errors?
Thus, questions from self-assembly combine theory of computation,
complexity, algorithmic questions, and coding in an interesting way.
In this two-talk overview series, I plan to give a taste of the
models, questions, and known results.
-- David Kempe <kempe@cs.washington.edu> _______________________________________________ Theory-group mailing list Theory-group@cs.washington.edu http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Tue Apr 27 2004 - 16:40:01 PDT