Christos Papadimitriou

Christos Papadimitriou studied at Princeton University and National Technical University of Athens. The recorded working language is English and Modern Greek. The field of work recorded is computer science. Employment is recorded with Harvard University, Massachusetts Institute of Technology and University of California, Berkeley. Works named in the authority record are A simple algorithm for finding frequent elements in streams and bags. Distinctions recorded are Knuth Prize, Gödel Prize, EATCS award and IEEE John von Neumann Medal.

• Name — Christos Papadimitriou • Birth Name — Christos Charilaos Papadimitriou • Born — 16 August 1949 • Birthplace — Athens, Greece • Fields — * Algorithms • Complexity • Game theory • Education • Evolution • Workplaces — * University of California, Berkeley • Columbia University • Harvard University • MIT • National Technical University of Athens • Stanford University • UCSD • Education — * National Technical University of Athens (MEng) • Princeton University (PhD) • Thesis Title — The Complexity of Combinatorial Optimization Problems • Thesis Url — http: dl.acm.org/citation.cfm?id=908113 • Thesis Year — 1976 • Doctoral Advisor — Kenneth Steiglitz • Doctoral Students — * Constantinos Daskalakis • Paris Kanellakis • Elias Koutsoupias • Joseph Mitchell • Christopher Umans • Yaron Singer • Awards — * Von Neumann Medal (2016) • EATCS Award (2015) • Gödel Prize (2012) • IEEE Computer Society Charles Babbage Award (2004) • Knuth Prize (2002) • Website — http: www.cs.berkeley.edu/~christos

Papadimitriou studied at the National Technical University of Athens, where in 1972 he received a degree in electrical engineering through an integrated master's program. He then pursued graduate studies at Princeton University, where he received his PhD in electrical engineering and computer science in 1976 after completing a doctoral dissertation titled "The complexity of combinatorial optimization problems."

Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, UCSD, University of California, Berkeley and is currently the Donovan Family Professor of Computer Science at Columbia University. Papadimitriou co-authored a paper on pancake sorting with Bill Gates, then a Harvard undergraduate. Papadimitriou recalled "Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: 'Such a brilliant kid. What a waste.'" The company was Microsoft. Papadimitriou co-authored "The Complexity of Computing a Nash Equilibrium" with his students Constantinos Daskalakis and Paul W. Goldberg, for which they received the 2008 Kalai Game Theory and Computer Science Prize from the Game Theory Society for "the best paper at the interface of game theory and computer science", in particular "for its key conceptual and technical contributions"; and the Outstanding Paper Prize from the Society for Industrial and Applied Mathematics. In 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. Also in 2002, he became a member of the U.S. National Academy of Engineering for contributions to complexity theory, database theory, and combinatorial optimization. In 2009 he was elected to the US National Academy of Sciences. During the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), there was a special event honoring Papadimitriou's contributions to computer science. In 2012, he, along with Elias Koutsoupias, was awarded the Gödel Prize for their joint work on the concept of the price of anarchy. Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory. He has also co-authored the textbook Algorithms (2006) with Sanjoy Dasgupta and Umesh Vazirani, and the graphic novel Logicomix (2009) with Apostolos Doxiadis.

At UC Berkeley, in 2006, he joined a professor-and-graduate-student band called Lady X and The Positive Eigenvalues.

Christos Papadimitriou worked in computer science. He was employed by Harvard University, Massachusetts Institute of Technology, University of California, Berkeley, University of California, San Diego and Stanford University. He belonged to National Academy of Sciences, American Academy of Arts and Sciences, National Academy of Engineering, Association for Computing Machinery and Academia Europaea.

Christos Papadimitriou is recorded with the occupation university teacher. Recorded with the occupation computer scientist. Recorded with the occupation prose writer. Recorded as writer, mathematician, computer scientist, university teacher and musician.