Newtonpedia ES
Home › Computing › Christos Papadimitriou
Christos Papadimitriou
Image: Wikimedia Commons

Christos Papadimitriou

Greek-American theoretical computer scientist specializing in computational complexity and game theory · 1949

Born
August 16, 1949
Country
United States, Greece
Section
Computing

Biography

Christos Charilaos Papadimitriou (born 16 August 1949) is a Greek-American theoretical computer scientist. His work asks two basic questions: which problems a computer can solve at all, and how much effort it takes to solve them. Over several decades his research has shaped computational complexity theory, combinatorial optimization, database research and, more recently, the game theory behind internet markets and online systems.

He studied at the National Technical University of Athens, where he earned a degree in electrical engineering in 1972 through an integrated master's programme. He then moved to Princeton University, completing a master's degree in 1974 and a PhD in electrical engineering and computer science in 1976. His doctoral dissertation was titled “The complexity of combinatorial optimization problems”. Combinatorial optimization means choosing the best option from a huge number of possible combinations, such as finding the shortest route through many cities. That question, which sounds narrow, became a thread running through much of his later work.

His teaching career took him to some of the most prominent universities in the world. He has taught at Harvard, at MIT, at his alma mater in Athens, at Stanford, at UC San Diego and at the University of California, Berkeley. He is currently the Donovan Family Professor of Computer Science at Columbia University.

Complexity theory studies how much time and memory an algorithm, a step-by-step procedure, needs as the size of a problem grows. Some problems can be solved quickly even when they become very large; others grow so fast that even the most powerful computers would take an unreasonable time to finish them. Papadimitriou helped to map that boundary. His textbook “Computational Complexity”, published in 1994, became one of the most widely used books in the field and remains a standard reference for students and researchers.

Earlier, in 1982, he had co-written two foundational texts. One, with Kenneth Steiglitz, was “Combinatorial Optimization: Algorithms and Complexity”. The other, with Harry R. Lewis, was “Elements of the Theory of Computation”, an introduction to the mathematical foundations of computing. In 1986 he published work on database concurrency control, which deals with how a database keeps simultaneous operations on the same data from producing wrong results. In 2006 he co-authored the textbook “Algorithms” with Sanjoy Dasgupta and Umesh Vazirani, which is also widely used in university courses.

Some of his best-known results came from collaboration with his students. With Constantinos Daskalakis and Paul W. Goldberg, he showed that computing a Nash equilibrium, a situation in which no player can do better by changing strategy alone, is computationally hard. For that paper the three received the 2008 Kalai Game Theory and Computer Science Prize, and an outstanding paper award from the Society for Industrial and Applied Mathematics. In 2012, together with Elias Koutsoupias, he received the Gödel Prize for the concept of the “price of anarchy”, a measure of how much worse the overall outcome can become when each participant pursues only their own interest.

He has also written for a general audience. In 2009 he published the graphic novel “Logicomix” with the writer Apostolos Doxiadis, a book about the search for truth in the foundations of mathematics and logic. A small episode from his early career involves Bill Gates. While Gates was an undergraduate at Harvard, the two wrote a paper on pancake sorting, the problem of arranging a stack of pancakes of different sizes using only flips of the top portion. Papadimitriou later recalled that, two years afterwards, he called Gates to share news of the paper's acceptance and learned that Gates had moved to Albuquerque to run a small company writing software for microprocessors. That company was Microsoft. Papadimitriou admitted that he had thought it was a waste of a brilliant student, a remark that now reads rather differently. In 2006, while at Berkeley, he joined a rock band made up of professors and graduate students called “Lady X and The Positive Eigenvalues”.

His professional recognition is extensive. He was named a Fellow of the Association for Computing Machinery in 2001 and received the Knuth Prize in 2002. The same year he was elected to the US National Academy of Engineering for his contributions to complexity theory, database theory and combinatorial optimization. In 2009 he was elected to the US National Academy of Sciences. He holds honorary doctorates from ETH Zurich (1997), the National Technical University of Athens (2011) and the École polytechnique fédérale de Lausanne (2013). He received the IEEE John von Neumann Medal in 2016 and the Harvey Prize of the Technion in Israel in 2019, for the year 2018.

His legacy is twofold. He has trained many researchers who have carried complexity theory and game theory into practical areas such as online advertising, network design and digital markets. His textbooks and writing for general readers have also made difficult ideas available to people outside the specialist community.

Main contributions

  • 1982Elements of the Theory of Computation (with Harry R. Lewis): a textbook on the mathematical foundations of computing.
  • 1982Combinatorial Optimization (with Kenneth Steiglitz): a book on how to choose the best solution among very many possible combinations and how hard that choice is to compute.
  • 1986Work on database concurrency control, which prevents simultaneous operations on the same data from producing wrong results.
  • 1994Computational Complexity: a reference book on how much effort algorithms need to solve different problems.
  • 2006Algorithms (with Sanjoy Dasgupta and Umesh Vazirani): a university textbook on designing and analysing algorithms.
  • 2009Logicomix (with Apostolos Doxiadis): a graphic novel about the search for truth in the foundations of mathematics and logic.
  • 2012Gödel Prize for the concept of the “price of anarchy”, which measures how much worse the overall outcome becomes when each participant pursues their own interest.
  • With Daskalakis and Goldberg, a proof that computing a Nash equilibrium is computationally hard.

Teachers and students

Studied under:

Taught:

Paris KanellakisJoseph S. B. MitchellElias KoutsoupiasChris UmansConstantinos DaskalakisEsther ArkinVangelis PaschosAlan Glenn MurrayXiaotie DengKamalika ChaudhuriAlex FabrikantStephen A. VavasisEdouard Louis Servan-SchreiberDeborah Gail GoldmanKunal TalwarJames R. LeeChristos Alexandros PsomasZiv Bar-YossefFrank BanYaron Singer

See their academic family tree →

Trivia and anecdotes

Bill Gates and pancakes

Papadimitriou co-wrote a paper with Bill Gates, then a Harvard undergraduate, on sorting pancakes by flipping only the top portion of the stack. By his own recollection, Gates had already left to run a small software company that became Microsoft.

An academic rock band

In 2006, while at Berkeley, he joined an underground rock band made up of professors and graduate students, called “Lady X and The Positive Eigenvalues”.

Mathematics as a comic

“Logicomix” presents the search for truth in logic and mathematics as a graphic novel, an unusual format for a book on these subjects.

Their contemporaries

While Christos Papadimitriou was alive (1949–)…

Alive at the same time

Discovered or invented in those years

  • 1957
    Artificial satelliteAn artificial satellite is a human-made object placed in orbit around a celestial body, usually Earth, to collect information, relay signals, or carry out a specific task.
  • 1969
    InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
  • 1971
    EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
  • 1973
    Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
  • 1989
    World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.
  • 1990
    Web browserA program that lets people access the web by fetching a page's files from a server and displaying them on screen as an interactive page.

See this life on the timeline →

More people in Computing