Elegantly Complex

You studied electrical engineering first, what drew you to computer science in grad school?

Computers solve problems in real life by running algorithms, precise sequences of instructions. And yet there are those problems, that we would love to solve by computer, but we cannot because the only algorithms we have for them require exponential time and are therefore useless. Complexity theory is the mathematical understanding of the reasons why this happens, the principled classification of computational problems as easy and hard. 

I started my research career as a student at Princeton in the early 1970s, when computer scientists had articulated the P vs NP question ("Is exhaustive search ever necessary?") and we had realized that some problems are inherently hard, impossible to solve exactly by computers within a reasonable time. 

We started to explore the world of computation equipped with this new understanding, we made progress and discovered structure, but eventually we encountered new difficulties. When you seek to understand complexity in more and more sophisticated contexts and corners of the world, you find that the world does not always conform to the shape of the P vs NP problem. There are many more textures and shades of complexity that you need if you want to map the world around us. To understand processes such as evolution and social interaction, or the process of approximating the best solution of a problem, you need to refine your understanding of complexity. 

During the 1980s and 1990s I worked with Mihalis Yannakakis—my life-long friend and now my colleague here at Columbia—to define nuances of the P vs NP problem that would better capture these phenomena. I was based in California (first Stanford University, then UC San Diego) and he at Bell Labs in New Jersey, but we would work together all the time on these research fronts, also on others. Decades later that work culminated in our understanding of the important fact that the Nash equilibrium—a most central concept in economics—is an intractable problem. This time the two of us wrote two independent and complementary papers.

Over the past 40 years, what are some of the career highlights that stand out for you?

I came to the United States in 1973, after my undergrad years in Greece and one horrific year in the Greek army. Those were the dark, oppressive years of the dictatorship in Greece, and I was fleeing that hell. Others stayed and resisted it, eventually they made a difference, a few were murdered along the way. I fled. That was a J. Conrad-like moment that has been haunting me all my life. In my novel Independence I remember, in a fictional setting, that long, dark night of my youth.

I had a student visa, but I was essentially a political refugee. I slowly started grad school in a new discipline I knew very little about, planning to look around, to explore opportunities outside the campus. And that very moment, out of nowhere, complexity grabbed me. I found this new field absolutely fascinating and beautiful, an answer to all my intellectual prayers. Within a year I had proved something I thought was fun but my professors found remarkable. The traveling salesman problem is an old puzzle: you are given many points in the plane, and you are asked to find the shortest route that visits them all. The traveling salesman problem was literally the only thing I knew about this field before I was admitted to grad school. I came up with a proof that it belongs to this class of “NP-complete” problems, impossibly hard nuts that seem to require exponential time to crack (a concept which had been discovered by U of Toronto’s Stephen Cook and UC Berkeley’s Richard Karp a couple of years earlier).

Fast forward a quarter of a century. The year is 1996, I am at the apex of my career, to use an old cliché. The complexity research with Mihalis is behind me and my graduate textbook on complexity is out. For me, writing a book about a subject is an act of separation, a sign that I am seeking closure, looking for something new. I have just moved to Berkeley, a university that I had loved as a postdoc, and the intellectual and social intensity of that campus, its aggressive and pervasive form of academic freedom, is getting under my skin. 

That very moment I looked around me, and I suddenly realized: The world has changed. The internet was in its baby years, but for me it already hovered above me bigger than life: a fascinating, complex, sprawling artifact whose workings and evolution and growth are not the result of clever software and hardware alone, but of the hopes, fears, incentives, ambition, longings, curiosity, and complex decisions of a million users, programmers, providers, entrepreneurs. 

A decade earlier, my Stanford colleague Kenneth Arrow – a truly great man who left us recently – had inspired and encouraged me to look into computational aspects of economics, but now this has become urgent and center stage. Two and a half decades later, there is a thriving field called algorithmic game theory, at the interface of computer science, game theory, economics, and the internet – and Columbia, incidentally, is a superpower in this arena. I am very proud of this.

What direction has your research taken recently?

Five years ago I became interested in the brain. How does the brain beget the mind? How do neurons and synapses and molecules orchestrate behavior, language, intelligence, reasoning? There are difficult problems in science, there are hard, challenging problems, and then there is this. In the midst of the on-going explosion of new knowledge in neuroscience, I can see no real progress on the overarching question. We need a new framework. In the words of my Columbia colleague Richard Axel, my hero in this business, in order to fathom the ways in which neural activity becomes thought we need a new “logic” – a formal system!  I have some cool ideas and some great collaborators.

You’ve been described as a “master teacher.” What kinds of classes are your favorite to teach?

Last semester I taught algorithms, the wellspring of all computation. I will never get tired of introducing my students—mostly undergrads—to the magic of algorithms, to the excitement of finding clever new ways for solving problems by computer—and to the totally cool math that gets you there.  

The previous semester I taught a graduate seminar on my new research interest, “Computation and the Brain,” and it was the hardest thing that I have ever done. I had to work three full days for every lecture, to absorb new material and figure out how you teach it to a class with diverse backgrounds. But it was well worth it – and I am hoping for the students too. 

The coming fall I am teaching this seminar again, and I think that this time it is going to be pure fun and excitement, last year’s hard work will finally bear fruits for me and my students. I am planning to dedicate a large part of the course to the mystery of language in the brain – last year I barely had time to touch it. Maybe a book will come out of this…

If you had to peer into your crystal ball, what do you think the future holds for us?

In the world of technology? It will be unlike anything anybody can predict. Listen, as I told you, I am proud that I saw the potential of internet very early. And yet, when I moved from Berkeley to Columbia two years ago, I had to throw away several old books, among them one published in 1995 and titled The Whole Internet.  I held this book in my hand and I felt humbled: So, in 1995 I was so hopelessly naïve that I thought the internet could be contained in a book! 

A little later than 1995, the debate in information technology (IT) was whether the internet platform of the future would be the TV or the desktop. And I can imagine dozens of clever executives in the IT industry arguing about this conundrum back and forth, shouting at each other in their Nokia cellphones – and none of them looked at the true platform of the future, in their hand. The future of IT is impossible to see even when you are holding it in your hand. I knew about Google and Facebook from day one, I appreciated the power of their game, but never imagined their current status. The future will surely surprise you.

As for the rest of the world… It’s easy to get depressed by the news, by the political choices and social attitudes of your fellow humans all over the world, by a cast of world leaders who are, frankly, gross caricatures – refreshing exceptions like New Zealand notwithstanding. By the state of the world at large, the twin looming menaces of planet decay and inequality, feeding into all of our other problems. Even the internet, only twenty years ago a utopia of universal information, equal opportunity, companionship, and democracy, is plagued by grave problems of privacy and exploitation, of polarized deception and unequal access.

But there are also signs of hope. My students these years seem to me much more idealistic, wise, and world-minded than a couple of decades ago (but then, I have only taught at Columbia and UC Berkeley…). To me, the most mature people on the planet seem to be the high school students in Europe striking for planet survival. Perhaps the world’s problems will get on a better track once the millennial women and men assume power – and this does not necessarily have to wait for very long.