TCS+ Talk

Join us to watch this  TCS+ video talk. Coffee & pastries will be served to make up for the early time.

Abstract: Consider the following thought experiment: a random population of truth assignments of a Boolean function F with n variables reproduces with recombination, where satisfying truth assignments have a small fitness advantage (that is, they are slightly more likely than nonsatisfying ones to reach adulthood and reproduction). Recombination means that the offspring picks the value of each variable from either parent. Will satisfaction eventually become ubiquitous in the population? In polynomially many generations, and with polynomially large population (by "polynomial" we mean polynomial in n and the inverse initial probability of satisfaction)? And if so, would this result tell us anything informative about the way in which complex features depending on many genes emerge in a species?