Worldly Computation: Q&A With Christos Papadimitriou

Oct 18 2018 | By Joanne Hvala | Photo Credit: Timothy Lee Photographers | Logicomix Cover Courtesy of Bloomsbury | Independence Cover Courtesy of Amazon

One of the world’s leading computer science theorists, Christos Papadimitriou is widely known for his research in computational complexity, helping to expand its methodology and reach, as well as authoring the preeminent textbook on the subject. Viewing other fields through an “algorithmic lens,” he has contributed to biology, economics, game theory, artificial intelligence, robotics, networks, and the internet—and most recently, to exploring the brain, which he calls the “ultimate algorithmic, scientific object of study.” At the same time, he has written or cowritten three novels, including the New York Times science fiction best seller Logicomix.

A master teacher, Papadimitriou joined Columbia Engineering a year ago as the Donovan Family Professor of Computer Science after more than 20 years at UC Berkeley. Prior to that, he also taught at Harvard, MIT, Stanford, and UC San Diego, as well as at Athens Polytechnic in his native Greece.

Last May, he was selected to give the Archimedes Lecture, a signature Columbia Engineering event that highlights outstanding research. Writing from the island of Icaria this summer, he shared his thoughts with Columbia Engineering on his journey from electrical engineering to computer science to neuroscience, and from the West Coast to the East.

Christos Papadimitriou

You have said “computation is worldly,” and you urge your students to take courses in economics, biology, sociology, psychology, linguistics, and the humanities. Why?

Computer science is a very young field—a baby, when compared with mathematics—and yet its brief history is already divided into two periods: before and after the advent of the internet, roughly a quarter century ago. The internet is the most fascinating of artifacts: it is alive, ubiquitous, powerful, mysterious. It was never designed—unlike all other engineering artifacts it is a gestalt; it emerged from the complex interactions of millions of engineers, governments, users, entrepreneurs, content providers. The internet is what computer scientists have studied these past two decades, while the computer has been reduced to the role of the lucky gadget that brought the internet to the world.

You are an electrical engineer by education. What first drew you to computer science?

The luckiest moment of my life. In 1972 I had no idea computer science existed. I applied to grad school to flee the oppressive dictatorship in Greece, and Princeton’s EE department pigeonholed me into their small computer science group—probably through misunderstanding my English. It took me only a month to realize that this was the discipline I had been dreaming to exist—and that I was good at it.

Papadimitriou’s works of fiction include the graphic novel Logicomix and most recently Independence, a novel set in Greece during its seven-year military dictatorship.

You are the author of three novels. What prompted you to start writing fiction?

I started writing overnight. I had never written a short story or a poem. Then, in the summer of 1997, I was in Greece and went to see a movie titled Cavafy, on the life of my favorite poet. I didn’t like it much, and yet I was curiously inspired by it. “Here is an artistic tribute to an intellectual hero,” I thought. And right there, in the theater lobby, I saw a blue-covered paperback hovering above, and its title was Turing. Alan Turing is the founder of computer science, my hero in both science and life. That night I started working on the plot, and a few days later, during my flight to the States, I penciled a draft of the first chapter (taking place, as it happens, in an airplane). It was the summer of 1997. I did not stop writing until the book was done. A steamy love story placed in the near future, a mysterious computer program whose name is Turing—plus a gentle introduction to the basic concepts of computation.

After Turing was published, my editor insisted that I meet fellow Greek author Apostolos Doxiadis, a Columbia alumnus who had just written a vaguely similar novel on mathematics. During our first meeting, in the summer 2001, we decided to write what became Logicomix. It took us nine years to complete this complex project, a graphic novel involving the collaboration of two writers and two artists. Its success (it stayed on the New York Times best seller list for a dozen weeks and was translated into more than thirty languages) was as gratifying as it was surprising to me—after all, it is a book about a technically advanced subject: the search for the logical foundations of mathematics in the beginning of the 20th century. . . . After Logicomix, I realized I had to write a novel about modern Greece—especially about the years of the dictatorship—that is at the same time a novel about revolution and about chance. This is how Independence was born.

Are you writing fiction now?

Of course I am, and this time I am writing in Greek. Once more I have a coauthor, except this time it’s my wife, Martha Sideri. On another front, I am planning out a sequel to Logicomix, a graphic novel about the most fascinating intellectual story of the 20th century—the dawn of the computer and the whirlwind lives of its creators, Turing and von Neumann. Tentatively titled The Birth, it’s at the earliest possible stage: the search for an artist collaborator . . .

I don’t think I will ever stop writing stories. Writing is sublimely addictive, and very much like spectacularly successful psychoanalysis. You understand hidden and crucial truths, a few of which you get to put on paper. You cry a lot. Back when I started, I was relieved that I did not have to quit my professorship to write fiction— if I had to, I suspect I might have.

You have said that writing fiction made you aware of how important stories are in science, and specifically to your own science. What makes for a good story, in your opinion?

Stories, like organisms, are good to the extent that they can survive and evolve. A story must speak to the foundations of the human existence shared by all of us and ride the zeitgeist without becoming topical. Incidentally, teaching through stories is not a new, clever idea; stories used to be the only way to teach: for 99 percent of our history, the village storyteller was the source of all knowledge. Schools and universities are a rather recent—and inconclusive—experiment . . .

You pride yourself on teaching and are seen as a master teacher. How do teaching and research inform each other?

Teaching is a higher stage of understanding— perhaps surpassed only by textbook writing. I know that I have understood a research subject only after I have taught a graduate course on it. Case in point: in the fall I am teaching for the first time a graduate course on Computation and the Brain. But teaching even basic undergrad courses is inspiring, makes you rethink.

What prompted your recent shift into neuroscience?

Computers and the internet make you see the world under a new light—an algorithmic light. When computer scientists look at a hard problem in another field, occasionally novel insights happen. The same way that, since the 17th century, mathematics has given us a new way of looking at science. Over the past thirty years I have been interested in economics, and in the past decade I have worked on evolution. Then it occurred to me that the brain is the ultimate algorithmic, scientific object of study.

Understanding the brain seems to me the hardest problem in all of science today. Despite tremendous progress, we do not seem to be getting closer to answering the overarching question: how does the brain beget the mind—cognition, behavior, intelligence, language, logic, stories? I believe that the answer will be at least partly computational, and computer scientists must work on this.

Where do you think your research will take you next?

When the internet arrived I was elated, motivated to make it the main subject of my research. I saw it as an unprecedented opportunity for computation to bring about a new era of liberation and equality for humanity. Twenty years later I am sorely disappointed—and I am not alone. The internet has become a vast plantation where data is the cash crop. For the privilege of running some cool software we give up our freedom to own our lives—our data. But a new internet architecture is on the rise, challenging and threatening this status quo, based on distributed consensus, communal ownership of data, and cryptography. I am beginning to think about blockchains.

After so many years at UC Berkeley, what prompted your move to Columbia Engineering?

I spent 22 wonderful and transformative years at that amazing university. Much of what I am I owe to Berkeley. But a time comes when you either move on or get stuck. Columbia has many of the things that I loved in Berkeley: towering academic excellence, academic freedom, emphasis on education, a radical tradition. Plus a few things Berkeley did not have: top neuroscience, New York City, and Mihalis.

You’ve had a long collaboration with Mihalis Yannakakis. What’s sustained that collaboration for so long? How would your work have been different if you hadn’t found such a brilliant collaborator?

Mihalis and I went to the same high school and the same university (both in Greece), and the same grad school (Princeton, where we met), except that he was two years behind me. I worked very hard to attract him to the then obscure field of computer science. I remember that, once I succeeded, the thought crossed my mind: even if I do no more computer science, by converting Mihalis I have done enough for the field. Our shared background, values, aesthetics, experience, and of course our friendship; they all render our communication channel fantastically efficient. Our collaboration is very smooth and sometimes eerily productive. Once, I visited him for an hour and a half at Columbia, after a hiatus of many years, and we ended up writing a nice joint paper right then and there. Half of my ten best papers, and maybe half of his, are joint—and this is not common. I would not be who I am without Mihalis.

What do you do in your free time?

Mostly, think. I read fiction and listen to music—live, if I have a choice. I spend a couple of weeks every year on the island of Icaria: swimming, recharging, dancing at the village festivals, getting inspired by sunrises and sunsets.

Is there any question I haven’t asked that you would like to answer?

My favorite authors: Italo Calvino, Constantine Cavafy, Halldór Laxness, W. G. Sebald. Musicians: Kurt Cobain, Miles Davis, Eric Clapton, Markos Vamvakaris.