Theory Lunch this week

November 3, 2010 § Leave a comment

What can Darwinian evolution evolve, and how fast?
5 November 2010
12pm
Warren Alpert 563 – HMS
Leslie Valiant
School of Engineering and Applied Sciences
Harvard University

Abstract

Living organisms function according to complex mechanisms that operate in different ways depending on conditions. Darwin’s theory of evolution suggests that such mechanisms evolved through variation guided by natural selection. However, there has existed no theory that would explain quantitatively which mechanisms can so evolve in realistic population sizes within realistic time periods, and which are too complex.
We suggest such a theory. Evolution is treated as a form of computational learning from examples in which the course of learning is influenced only by the aggregate fitness of the current hypothesis on the examples, and not otherwise by specific examples. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not. The dilemma is, say in the context of input functions for gene expression, that if the function class is too expressive then no evolution algorithm will exist to navigate it, and if it is too restrictive then it will not support biology.
It is shown, for example, that in any one phase of evolution, where selection is for one beneficial behavior, monotone Boolean conjunctions and disjunctions are demonstrably evolvable over the uniform distribution, while Boolean parity functions are demonstrably not. The framework also allows a wider range of issues in evolution to be quantified.

TL schedule here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Theory Lunch this week at It Takes 30.

meta

%d bloggers like this: