United States – 2001

For outstanding contributions to complexity theory, database theory and combinatorial optimization.

Christos Papadimitriou is a professor in the Electrical Engineering and Computer Sciences Department at University of California, Berkeley. Before joining UC Berkeley in 1996, he taught at Harvard, MIT, Athens Polytechnic, Stanford, and University of California, San Diego. He serves on the Campus Advisory Board of the Berkeley Center for New Media.

Papadimitriou received the 2002 Knuth Prize from ACM SIGACT and the IEEE Technical Committee on the Mathematical Foundations of Computing for longstanding and seminal contributions to the foundations of computer science. In 2012 he and Elias Koutsoupias received the Gödel Prize for their joint work on the price of anarchy, a concept in game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. Papadimitriou is a Fellow of ACM and the National Academy of Engineering, and is a member of the National Academy of Sciences.

He co-authored a paper, "Bounds for Sorting by Prefix Reversal," with Microsoft co-founder Bill Gates, while Gates was studying at Harvard.