Speaker: Christos H. Papadimitriou (University of California at Berkeley, USA)

Abstract

The idea of the algorithm, present in the work of Euclid, Archimedes, and Al Khorizmi, and formalized by Alan Turing only eight decades ago, underlies much of the realm of science – physical, life, or social. Algorithmic processes are present in the great objects of scientific inquiry – the cell, the universe, the market, the brain – as well as in the models developed by scientists over the centuries for studying them.

During the past quarter century this algorithmic point of view has helped make important progress in science, for example in statistical physics through the study of phase transitions in terms of the convergence of Markov chain Monte carlo algorithms, and in quantum mechanics through the lens of quantum computing.

In this talk I will recount a few more instances of this mode of research. Algorithmic considerations, as well as ideas from computational complexity, revealed a conceptual flaw in the solution concept of Nash equilibrium ubiquitous in economics. In the study of evolution, a new understanding of century-old questions has been achieved through purely algorithmic ideas. Finally, current work in theoretical neuroscience suggests that the algorithmic point of view may be invaluable in the central scientific question of our era, namely understanding how behavior and cognition emerge from the structure and activity of neurons and synapses.