Computational Insights and the Theory of Evolution

Christos Papadimitriou
U.C. Berkeley

I shall discuss recent work (much of it joint with biologists Adi Livnat and Stanford's Marcus Feldman, and more recently with Greg Valiant) on some central problems in Evolution that was inspired and informed by computational ideas. Considerations about the performance of genetic algorithms led to a novel theory on the role of sex in Evolution based on the concept of mixability. And a natural random process on Boolean functions can help us understand better Addington's genetic assimilation experiments, in which an acquired trait becomes genetic, and also to demonstrate a process whereby a novel advantageous trait can emerge in the whole population, without the spreading of mutations.

Slides:

Download slides for this talk in PDF format.

About the speaker:

Christos Papadimitriou is the C. Lester Hogan Professor of EECS Computer Science Division of the University of California at Berkeley. He is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory. He is interested in the theory of algorithms and complexity, and its applications to databases, optimization, AI, networks, game theory, and evolution.

Contact information:

Christos H. Papadimitriou
Computer Science Division, University of California at Berkeley
Soda Hall 689
Berkeley, CA 94720, U.S.A.
(510) 642-1559
email: christos (at) cs.berkeley.edu