People of ACM - Christos Papadimitriou
March 19, 2013
In this installment of "People of ACM," we are featuring Christos Papadimitriou.
Christos Papadimitriou is a professor in the Electrical Engineering and Computer Sciences Department at University of California, Berkeley. Before joining UC Berkeley in 1996, he taught at Harvard, MIT, Athens Polytechnic, Stanford, and University of California, San Diego. He serves on the Campus Advisory Board of the Berkeley Center for New Media.
Papadimitriou received the 2002 Knuth Prize from ACM SIGACT and the IEEE Technical Committee on the Mathematical Foundations of Computing for longstanding and seminal contributions to the foundations of computer science. In 2012 he and Elias Koutsoupias received the Gödel Prize for their joint work on the price of anarchy, a concept in game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. Papadimitriou is a Fellow of ACM and the National Academy of Engineering, and is a member of the National Academy of Sciences.
He co-authored a paper, "Bounds for Sorting by Prefix Reversal," with Microsoft co-founder Bill Gates, while Gates was studying at Harvard.
You teach Computer Science and you write novels. What is the connection?
There is a secret link between programming and storytelling. One day we'll read that neuroscientists discovered the two engage the same part of the brain. Writing a novel, especially near the end, when dozens of balls are hovering in the air and each must fall at exactly the right place, is close to what happens in coding—and in crafting an involved mathematical proof.
There are more connections: Teaching Computer Science is more effective and fun if it is intermingled with stories. I often stop in class to tell a story that animates the algorithm—like Theseus and the Minotaur for depth-first search—or about the discoverer of the algorithm or idea. How can you teach undecidability without recounting the tumultuous life and tragic death of Alan Turing? Or teach introduction to programming without mentioning Lady Ada?
Another connection is personal: My stories are often about computation. My first novel was Turing. My second, Logicomix, is a graphic novel about the crisis in mathematics in the early 20th century, which brought about the birth of the computer.
You mentioned twice Alan Turing, whose centennial we celebrated last year. How has he influenced you?
Turing has been the shining light of my career (see "Alan and I," CACM September 2012). Studying Electrical Engineering in Greece, I stumbled upon the Turing machine, and it transformed me intellectually. Turing's research legacy, automata theory, was my first topic in grad school at Princeton—where, as it turns out, I lived for two years in a dorm room rumored to be Turing's old quarters. The exacting rigor of his thought, his eerie talent for asking the right question, his amazing breadth of interest from hardware to biology, were major inspirations. Without my Turing fascination I would have never written stories, which would have left me missing a dimension.
You collaborated with Bill Gates in the 1970s. What impression did he make on you?
When I was an assistant professor at Harvard, Bill was a junior. My girlfriend back then said that I had told her: "There's this undergrad at school who is the smartest person I've ever met."
That semester, Gates was fascinated with a math problem called pancake sorting: How can you sort a list of numbers, say 3-4-2-1-5, by flipping prefixes of the list? You can flip the first two numbers to get 4-3-2-1-5, and the first four to finish it off: 1-2-3-4-5. Just two flips. But for a list of n numbers, nobody knew how to do it with fewer than 2n flips. Bill came to me with an idea for doing it with only 1.67n flips. We proved his algorithm correct, and we proved a lower bound—it cannot be done faster than 1.06n flips. We held the record in pancake sorting for decades. It was a silly problem back then, but it became important, because human chromosomes mutate this way.
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."
What advice would you give to budding technologists considering a career in computing?
I chose computing forty years ago, and it is one of the few choices I would repeat in a millisecond. These years were invaluable, singular, fascinating. I would trade them for nothing—save the next 40 years. Actually I don't have to trade, I plan to be there.
Computation has transformed itself radically a dozen times. It's like celestial mechanics, the chaos created by the strong interactions among three bodies: Science - industry - market. When I started computers were rooms, compilers a mystery, and Unix a strange new idea. The design of databases and chips became towering problems of the day. Parallelism came and went—and then came back. Robots, ditto. At first there were no networks, and then they were shaped as rings. AI was the world's most fascinating problem, then a problem nearly solved, then an embarrassment, and then promising, then not, until it thrived under another name. You must be ready to jump to a new raft—with both feet—a couple of times every decade. You must be constantly on the watch for the new huge thing. And be prepared to miss it, as I did with personal computers and Microsoft.
Computer Science was an adolescent, insecure field looking inward, trying to overcome its existential problems, to build a reputation, introverted by necessity, geeky by character. Then "the Internet" happened. Computation became the default platform of the universe. Today Computer Science is at the center of scientific discourse. 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.
All this makes computation the perfect subject for women. Clichés die hard, and entering freshmen are proverbially conformist when choosing majors, but I predict that computation will have a male majority for another twenty years at most, and then things will flip.