Christos Papadimitriou: Four decades of exploring the boundaries of computation

The renowned computer scientist and polymath Christos Papadimitriou has joined Columbia’s Computer Science Department as The Donovan Family Professor of Computer Science. He begins teaching this fall.

Over four decades, Papadimitriou’s research has explored two of the most fundamental questions in Computer Science: How quickly can computers solve problems? And what kinds of obstacles come in the way of such solutions? Fast algorithms—together with Moore’s Law, the astronomical increase of computer speed over the past six decades—have powered the Computer Revolution. Equally intriguing are problems that appear to resist fast solution because of some inherent complexity: Many are known to be NP-complete, a status suggesting that (unless P = NP, an eventuality most scientists agree is unlikely) all the computers in the world wouldn’t solve it in the lifetime of the universe. As a graduate student, Papadimitriou established this for the Euclidean traveling salesperson problem, a version of the classic problem where cities are points in the two-dimensional plane. Three decades later, with Paul Goldberg and Constantinos Daskalakis, Papadimitriou proved the hardness of computing a Nash equilibrium; in doing so he helped found the field of algorithmic game theory.

“Computation is worldly. It’s about society, markets, people, brains, behaviors,
perception, emotions. Computer Science is looking outwards now. I advise my
undergrad students to take as many courses as they can: Economics, biology,
sociology, humanities, linguistics, psychology.”
– Christos Papadimitriou

Papadimitriou’s contributions extend far beyond the theoretical realm. Complexity is everywhere—in the way protein folds, in the ways database queries are processed, in the structure and activity of neurons and synapses, in how information moves on the internet in the presence of diverse economic interests; on these and other topics Papadimitriou has applied insights from the world of computation to make new discoveries. Just last year, his research made headlines in the world of biology when he connected game theory and evolution to arrive at a novel theory on the role of sex in evolution.

“Christos is one of the most original thinkers in computer science,” says Mihalis Yannakakis, a frequent collaborator and long-time friend. “He has applied the computational lens to a wide range of fields, bringing in each one of them a new perspective, and leaving his mark by founding new research areas, introducing new models and concepts, and initiating research directions that have had a tremendous impact.”

“I started writing fiction quite suddenly, and it made me very aware of how important stories are in science, in my science.”        – Christos Papadimitriou

Unusual for a computer scientist, Papadimitriou engages the general public in the discussion of mathematical and computational ideas underlying science and technology. His 2003 novel Turing (A Novel about Computation) is a love story with an AI program as protagonist. His graphic novel Logicomix, coauthored with Apostolos Doxiadis, became an international best seller even though its central theme—Bertrand Russell’s attempts to establish a logical foundation for mathematics—is not an easy subject and Papadimitriou does not trivialize it. A third novel, Independence, wades into the political realm, following a family through the history of modern Greece

“There is nothing worth explaining that cannot be explained through a good story.”
– Christos Papadimitriou

He is fundamentally a teacher. His parents taught elementary and high school in Greece, and Papadimitriou himself has taught at Harvard, MIT, the National Technical University of Athens, Stanford, and the University of California at San Diego, and most recently at the University of California at Berkeley, where he found a home for 22 years. He is popular and sought after by students who rate him highly and note in particular his enthusiasm for the subjects he teaches. That Columbia students will now have the opportunity to learn algorithms and complexity theory from one of the foremost experts in the field is something the department is proud to offer. “We are absolutely delighted to have Christos joining us at Columbia,” says Julia Hirschberg, chair of the Computer Science Department. “He is a great scholar, teacher, and colleague!”

“Teaching is the only way I know to understand something.”
– Christos Papadimitriou

Papadimitriou has written extensively on a wide range of topics in computer science, as well as on problems in the natural, social and life sciences that have benefited from computational approaches: Artificial intelligence and learning, databases, optimization, robotics, control theory, networks and the Internet, game theory and economics, computational biology and the theory of evolution, and recently the Brain. He is author or coauthor of five textbooks—Computational Complexity, one of the most widely used textbooks in the field; Elements of the Theory of Computation with Harry Lewis; Combinatorial Optimization: Algorithms and Complexity with Ken Steiglitz; The Theory of Database Concurrency Control, and the undergraduate textbook Algorithms with Sanjoy Dasgupta and Umesh Vazirani—and hundreds of articles and blog posts.

Amongst the recognitions and awards accorded him: the fifth Knuth Award (2002) for longstanding and seminal contributions to the foundations of computer science; the Gödel Prize (2012) for joint work with Oxford’s Elias Koutsoupias on the concept of the price of anarchy. For contributions to complexity theory, database theory, and combinatorial optimization, he was made a member of the US National Academy of Engineering in 2002. He is a member also of the National Academy of Sciences and of the American Academy of Arts and Sciences. Last year he received the John Von Neumann Medal for “providing a deeper understanding of computational complexity and its implications for approximation algorithms, artificial intelligence, economics, database theory, and biology.”

At Columbia, Papadimitriou is looking forward to continuing and expanding his recent work on an algorithmic understanding of the brain with new colleagues at the Zuckerman Institute for Mind, Brain, Behavior. But above all, he cherishes the opportunity for more collaboration with Mihalis Yannakakis.

“It’s like coming back home, to a brother.”
– Christos Papadimitriou

BS in Electrical Engineering from Athens Polytechnic (1972), an MS in Electrical Engineering and PhD in EECS at Princeton (1974, 76 respectively)

Posted 9/11/2017
– Linda Crane