Machinations


Game Theory and Evolution
June 24, 2014, 8:14 pm
Filed under: Uncategorized | Tags: , , ,

The Game Theory of Life is a nice writeup of a recent PNAS paper Algorithms, Games and Evolution by Chastaina, Livnatb, Papadimitriou and Vazirani.  As a CS researcher with an amateur’s interest in biology, I really enjoyed this paper.

The paper shows a certain equivalence between two algorithms.  The first algorithm, I’ll call “evolution”.   This is an approximation (using replicator dynamics) to what happens in real Evolution in nature.  The second algorithm is the multiplicative weight update algorithm (MWUA) which we all know and love in CS.  MWUA is also known as weighted majority or winnow to many people in CS theory.

The paper proves that the outputs of “evolution” are equivalent to MWUA. They then show this implies that “evolution” is equivalent to a process that tries to maximize utility *plus* entropy (equation 3 in the paper). The utility part is not surprising since we’d certainly expect Evolution to be concerned with it.  The “plus entropy” part is surprising, and perhaps explains the surprising diversity of life.  Essentially sexual replication in the “evolution” algorithm is what gives rise to this additional entropy part.

I think it’s a pretty interesting paper. Intuitively, it proves that a simple kind of genetic algorithm (i.e. “evolution”) will give equivalent results to the MWUA (i.e. see the equivalence of Figures 1 d) and 2 d) in the paper). A nice result from the CS perspective.  However, there are a few “rah rah computer science” comments in the paper that may turn off some biologists.

I think the key thing that would really impress biologists would be making the “evolution” algorithm more realistic.  To do this would require improving Nagylaki’s theorem which is used in the paper for analyzing the “evolution” algorithm. The authors claim Nagylaki’s theorem can already be used to handle diploidy and partial recombination. Mutation is an area mentioned for future work. Modeling the interaction of organisms seems much harder. It’ll be interesting to see the followup work on this paper.

 



Secure Multiparty Computation Workshop
June 22, 2014, 10:48 pm
Filed under: Uncategorized | Tags: , ,

Last month I went to a  workshop on secure multiparty computation that was organized by IARPA.  I’ve had mixed luck with these types of workshops that are organized by funding agencies.  However, this one was pretty good, because of the timeliness of the topic, well-prepared talks, and the fact that the participants were some of the big names in security and MPC.

This was also one first times I’ve visited and given a talk at MIT, which was a lot of fun.  Many of the talk slides are included in the workshop link above.