Skip to content Skip to navigation
Pre-Defense
9/15/2016 03:00 pm
CoRE A (301)

The multiplicative weight updates method for evolutionary biology

Erick Chastain, Dept. of Computer Science

Defense Committee: Prof. Eric Allender (Chair); Prof. Rebecca Wright; Prof. Shubhangi Saraf; Prof. Nina Fefferman

Abstract

Recently there is much interest in the application of methods from the Theory of computation to evolutionary biology. Starting with the work of Christos Papadimitriou and Adi Livnat, there has been a concerted effort to use these techniques to analyze such diverse phenomena as: the algorithmic role of recombination to increase mixability, the evolution of modularity, and the evolution of complex adaptations. There is also work by Les Valiant and his students using tools primarily from learning theory to more broadly analyze evolutionary processes. In parallel, computer science theory has developed a novel method which has been applied in diverse areas of algorithms and complexity: the Multiplicative Weight Updates (MWU) method. The MWU method simply applies the MWU general-purpose online learning algorithm on problem-specific loss functions. The contribution of this thesis is to apply the MWU method and the algorithmic lens to make models in evolutionary biology.

The first contribution is a surprising equivalence between the MWU algorithm playing a coordination game and infinite-population genetics models with recombination and no mutation. By so doing, we resolve analytically a question asked by Papadimitriou and Livnat: whether mixability is increased in the short-term by recombination.

Other models introduced using MWU as a basic dynamics include a model of the Evolution of Animal personality and of tool use.

Finally, the thesis presents a novel connection between universal semantic communication and the Rivoire-Leibler model of population genetics, in addition to infinite population asexual selection models... with MWU as the key to proving the latter connection.