Reminder and time change - Mitsunori Ogihara's talk on 13 Dec.

[Margery Ishmael]

Please note: this talk will now take place at 3:00
instead of 2:30 as originally announced

DNA-Based Parallel Boolean Circuit Evaluation

Mitsunori Ogihara
University of Rochester

Wednesday, December 13, 3:00 pm
Ryerson Annex 276
(followed by refreshments in Ryerson 255)

Abstract:
DNA-based computation is a new field that integrates molecular biology and 
computer science. The goal of the field is to study the use of liquid-phase 
DNA for massively parallel computation. The potential of using DNA for 
computation lies in the fact that DNA has large
memory capacity (10^22 bits in one liter of DNA solution) and that 
biochemical operations are inherently parallel and dissipate little energy. 
The drawbacks are that biochemical operations are slow and sometimes 
error-prone.

A paper by Adleman in 1994 presented the first DNA-based algorithm, which 
is for solving the Hamilton Path Problem. Lipton extended Adleman's idea 
and showed that SAT, the basic NP-complete problem, could be solved using 
DNA. Since then, various DNA computational models have been proposed and 
many DNA-based algorithms have been
developed. Two most important issues in this field are to clarify the power 
of DNA-based computation and to find killer applications, i.e., the 
problems in which DNA are more efficient than silicon-based computers.

In this talk I will speak about simulation of logic-gates using DNA. First, 
I will show how one can simulate AND and OR using DNA and then based on the 
construction how one can evaluate the output of a Boolean circuit on a 
given input. Then I will discuss the issue of eliminating human 
intervention in circuit evaluation. Finally, I will talk about 
characterization of DNA-based computation in terms of Boolean circuit 
complexity.

Host: Stuart Kurtz


====================================================
Margery Ishmael
Department of Computer Science
1100 E. 58th St.
Chicago, IL 60637

tel: 773 834-8977  fax: 773 702-8487

marge at cs.uchicago.edu 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20001212/97e21adc/attachment.htm