Tata Institute of Fundamental Research
Algorithms, Games and Evolution
STCS Seminar
Speaker:
Umesh V. Vazirani (University of California at Berkeley
Department of Computer Science
Berkeley, CA 94720
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Monday, 16 Nov 2015, 11:30 to 12:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced all of life as we see it around us. Or stated from a computational perspective, what algorithm could possibly achieve Nature's solution to the problems of robotics, vision and theorem proving in about 10^12 generations (steps)? We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of recombination become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known to be surprisingly powerful and versatile. A dual description of MWUA shows that it maximizes a trade-off between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution (based on joint work with Erick Chastain, Adi Livnat and Christos Papadimitriou).
| Speaker: | Umesh V. Vazirani (University of California at Berkeley Department of Computer Science Berkeley, CA 94720 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Monday, 16 Nov 2015, 11:30 to 12:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced all of life as we see it around us. Or stated from a computational perspective, what algorithm could possibly achieve Nature's solution to the problems of robotics, vision and theorem proving in about 10^12 generations (steps)? We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of recombination become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known to be surprisingly powerful and versatile. A dual description of MWUA shows that it maximizes a trade-off between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution (based on joint work with Erick Chastain, Adi Livnat and Christos Papadimitriou).