Dr. Dobb's Journal - August 2008 - (Page 18)

Strategic Vision A CONVERSATION WITH CHRISTOS PAPADIMITRIOU DDJ: Where do you start looking at the Web and the Internet? Link networks? Semantics? CP: The Web and the Internet are two separate subjects, both fascinating and mysterious. Links are important. Content is important. The way routers and ISPs are linking on the Internet is important. They’re very organic. DDJ: John Gilmore said, “The Net interprets censorship as damage and routes around it.” CP: Very well said! I think we should be proud. The Internet embodies healthy principles of the programmers who came up with and implemented the protocols. If it’s democratic and censorship-resistant and open and end-to-end, all these great things that are under attack these days, it’s because of ingenious and strategic programming. DDJ: I guess you could model how rumors spread on the Internet. CP: There are a lot of people working on this. How rumors spread and how product preferences spread interests advertisers. Call it “information epidemiology.” Say you look at a network and try to decide which are the leader nodes to which you give a free sample of your product and conquer the market as a result. DDJ: Tell us about your paper “Algorithms, Games, and the Internet.” CP: This is about the interface between algorithm theory, networking and economics. When I say “games” I don’t mean “Guitar Hero.” I mean the Game Theory of John Nash, economic games. The paper was basically a call to arms to study this interface. I proposed a few problems. It had a result I am proud of. In 1950, Nash proved this theorem that every game has equilibrium. This had completely eluded the other great game theorists up to that time. Von Neumann suspected it was true but didn’t know how to prove it. This brought Nash the Nobel Prize almost 50 years later [1994 Nobel Memorial Prize]. So since Nash’s paper, everyone was curious how you find this equilibrium. This sounds like a job for a computer scientist. We did try to discover how hard it is to find the Nash Equilibrium. Nash’s theorem is an existence theorem, that equilibrium exists. If you want to find that equilibrium, to put it to work, you have to look at the proof. And the proof doesn’t help you here. The proof relies on another difficult theorem called Brouwer’s fixed-point theorem, which 18 Dr. Dobb’s Journal l www.ddj.com l August 2008 was proved 50 years earlier. Is the dependence on Brouwer intrinsic or is there a quick way to prove the existence of equilibria that would lead to an algorithm? Three years ago, with my students Constantinos Daskalakis and Paul Goldberg, we proved that these two great theorems of the 20th century, Brouwer and Nash, are equivalent, that you need Brouwer to prove Nash, and you can prove Nash from Brouwer. As a result, you can’t find Nash equilibrium, it possesses intrinsic difficulty. What a mathematician always dreams is that he will one day prove a theorem that will teach the world something they don’t know, that will point to a new direction. But what a mathematician does every day is prove what everybody knows is true but couldn’t prove. DDJ: You seem to be enunciating theories that do have an effect on the external world. CP: From my point of view, it’s humbling how little and how belated is the effect of anything one does. It’s a complex world! DDJ: Tell us about your novels. CP: I have written a novel called Turing (A Novel about Computation). It’s a modern love story in which the protagonist is an AI program called “Turing.” It started about 18 years ago. I discovered this was inside me and had to come out, so I took time to write it. I couldn’t resist it. It was one of the most powerful experiences I ever had. I found myself thinking about myself from every perspective. I worked hard, I cried a lot. I saw things in myself that were perhaps there before but I had never seen them. If I had not done it, I would be a less happy man. I shudder at the thought I might have lived my life without writing this novel. DDJ: Perhaps a way to let out the irrationality after all the rationality of mathematics? CP: Yes. Now I’m writing a graphic novel called Logicomics. It’s on the history of mathematical logic. DDJ: You encourage your students to read the classics. CP: The classics of computer science. It’s very instructive. It happens that my students sometimes realize there is something seriously broken in their field and they take time and fix it. What is fascinating reading these papers, you can see the author knows that it’s important, that they are writing history. Graduate students should see this and be inspired. Euler’s paper, written when he was quite young, on the Bridges of Konigsberg is the beginning of Network Theory, whether you can walk over each bridge once, saying that sometimes geometry is not important, the only thing that matters is what is connected to what. DDJ: Is Bridges of Konigsberg a version of the Traveling Salesman Problem? CP: Not quite. It’s like the Knight’s Tour, with the difference that the Knight goes to every island, but in the Bridges you have to cross every bridge; that is, traverse every edge. This turns out to be much easier than the Traveling Salesman. It’s one of these problems that look equally hard but has no intrinsic complexity, you can eyeball it. Euler’s classic serves to tell us that not everything that looks intrinsically complex is so. Another paper I like my students to read is where Feynman proposed quantum computers. I’m interested in the mathematics of quantum computing. It’s a beautiful question in mathematics, it’s a beautiful question in physics, it’s a beautiful question in computer science. You think quantum computing is about powerful computers, but quantum computing may prove to be about testing quantum physics, to find out why we cannot build these powerful computers. Who knows? Maybe there is something fishy with the theory. One of the reasons quantum computing is so interesting is that it looks at some extremely counterintuitive predictions of quantum theory. If building quantum computers fails on a practical engineering basis, that will be a disappointment, meaning the idea dies of a thousand cuts, it’s too difficult, we can’t afford it, we stop trying. But what would be fascinating is if there is a theoretical difficulty! There are physicists who see quantum computing as the ultimate test of quantum theory. This brings us back to where we started this conversation, the Algorithmic Lens. In some sense, Physics looks at itself and its most prestigious theory through the Algorithmic Lens. That’s a great triumph of the algorithmic programming way of thinking. DDJ http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - August 2008

Dr. Dobb's Journal - August 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook A Conversation with Christos Papadimitriou OpenGL and Mobile Devices: Round 2 Ellipse Specification Using Vectors Embed Custom GUIs in WPF Building RIAs on J2EE Foundations Disentangling Concepts in Object-Oriented Systems The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - August 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.