The Algorithmic Lens:
How the Computational Perspective is Transforming the Sciences

3:30 – 4:20pm, Friday, October 9, 2009
EEB 125
Christos Papadimitriou (UC Berkeley)


Computational research transforms the sciences (physical, mathematical, life or social) not just by empowering them analytically, but mainly by providing a novel and powerful perspective which often leads to unforeseen insights. Examples abound: quantum computation provides the right forum for questioning and testing some of the most basic tenets of quantum physics, while statistical mechanics has found in the efficiency of randomized algorithms a powerful metaphor for phase transitions. In mathematics, the P vs. NP question has joined the list of the most profound and consequential problems; in economics, considerations of computational complexity revise predictions of economic behavior and affect the design of economic mechanisms such as auctions. Finally, in biology some of the most fundamental problems, such as understanding the brain and evolution, can be productively recast in computational terms. My talk is structured around four vignettes exemplifying this pattern.

Note: This is an updated, and 60% new, version of a similar talk I have been giving over the past two years.