Christos Papadimitriou


One of world’s leading computer science theorists, Christos Papadimitriou is best known for his work in computational complexity, helping to expand its methodology and reach. He has also explored other fields through what he calls the algorithmic lens, having contributed to biology and the theory of evolution, economics, and game theory (where he helped found the field of algorithmic game theory), artificial intelligence, robotics, networks and the Internet, and more recently the study of the brain. 

He authored the widely used textbook Computational Complexity, as well as four others, and has written three novels, including the best-selling Logicomix and his latest, Independence. He considers himself fundamentally a teacher, having taught at UC Berkeley for the past 20 years, and before that at Harvard, MIT, the National Technical University of Athens, Stanford, and UC San Diego.

Papadimitriou has been awarded the Knuth Prize, IEEE’s John von Neumann Medal, the EATCS Award, the IEEE Computer Society Charles Babbage Award, and the Gödel Prize. He is a fellow of the Association for Computer Machinery and the National Academy of Engineering, and a member of the National Academy of Sciences.

He received his BS in Electrical Engineering from Athens Polytechnic in 1972. He has a MS in Electrical Engineering and a PhD in Electrical Engineering/Computer Science from Princeton, received in 1974 and 1976, respectively.

Tutorial: Computation and the Brain

Despite accelerating progress in experimental neuroscience, many researchers agree that we are making no progress in the field’s overarching question: “how does the brain compute?”  I will try to convey what I learned during my four years of pondering the question, to impart some useful background, and to explain an approach to the problem developed in collaboration with Santosh Vempala and Mike Collins.