Skip to content Skip to navigation
PhD Defense
12/8/2016 03:00 pm
CoRE A (301)

The Multiplicative Weight Updates method for Evolutionary Biology

Erick Chastain, Dept. of Computer Science

Defense Committee: Eric Allender (Chair); Rebecca Wright; Saraf Shubhangi; Nina Fefferman; Ruta Mehta (University of Illinois at Urbana-Champaign)

Abstract

A new and exciting direction of recent work in theoretical computer science is the application of methods from the field 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 innovation.

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.