Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before joining Berkeley in 1996 he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, AI, economics, evolution, and the Internet. He holds a PhD from Princeton, and honorary doctorates from ETH (Zurich), the Universities of Macedonia (Thessaloniki), Athens, Cyprus, and Patras. He is a member of the National Academy of Sciences, the American Academy of Arts and Sciences and of the National Academy of Engineering, and a fellow of the ACM. His second novel "Logicomix" has been translated in over 20 languages.

 

I shall discuss recent work (much of it joint with biologists Adi Livnat and Marcus Feldman) on some central problems in Evolution that was inspired and informed by computational ideas. Considerations about the performance of genetic algorithms led to a novel theory on the role of sex in Evolution based on the concept of mixability. And a natural random process on Boolean functions can help us understand better Waddington’s genetic assimilation phenomenon, in which an acquired trait becomes genetic.