TITLE: Papadimitriou, the Net, and Writing AUTHOR: Eugene Wallingford DATE: July 19, 2008 3:04 PM DESC: ----- BODY: I've been trying to take a break from the office and spend some time at home and with my family. Still, I enjoy finding time to read an occasional technical article and be inspired. While waiting for my daughter's play rehearsal to end last night, I read A Conversation with Christos Papadimitriou, a short interview in the August 2008 of Dr. Dobb's Journal. I first learned of Papadimitriou from a textbook of his that we used in one of my earliest graduate course, Elements of the Theory of Computation. Since that time, he has done groundbreaking work in computational complexity and algorithms, with applications in game theory, economics, networks, and most recently bioinformatics. It seems that many of the best theoreticians have a knack for grounding their research in problems that matter. The article includes several tidbits that might interest computer scientists and professional programmers of various sorts. Some are pretty far afield from my work. For instance, Papadimitriou and two of his students recently produced an important result related to the Nash Equilibrium in game theory (have you seen A Beautiful Mind?) Nash's theorem tells us that an equilibrium exists in every game, but it does not tell us how to find the equilibrium. Is it possible to produce a tractable algorithm for finding it? Papadimitriou and his students showed that Nash's theorem depends intrinsically on the theorem which is the basis of Nash's proof, which means that, in practice, we cannot produce such an algorithm; finding the Nash equilibrium for any given problem is intractable. The interview spent considerable time discussing Papadimitriou's recent work related to the Internet and the Web, which are ideas I will likely read more about. Papadimitriou sees the net as an unusual opportunity for computer scientists: a chance to study a computational artifact we didn't design. Unlike our hardware and software systems, it "emerged from an interaction of millions of entities on the basis of deliberately simple protocols". The result is a "mystery" that our designed artifacts can't offer. For a theoretical CS guy, the net and web serve as a research lab of unprecedented size. It also offers a platform for research at the intersection of computing and other disciplines, such as communication, where my CS grad student Sergei Golitsinski is taking his research. The interviewer quoted net pioneer John Gilmore in the same arena: "The Net interprets censorship as damage and routes around it." This leads to open questions about how rumors spread, an area that Papadimitriou calls "information epidemiology". One of my former grad students, Nate Labelle, worked in this area for a particular part of the designed world, open-source software packages, and I'd love to have a student delve into the epidemiology of more generalized information. I would also like to read Papadimitriou's novel, Turing. I recall when it came out and just haven't gotten around to asking my library to pick it up or borrow it. In the interview, Papadimitriou said,
I discovered this [novel] was inside me and had to come out, so I took time to write it. I couldn't resist it. ... If I had not done it, I would be a less happy man.
Powerful testimony, and the chance to read CS-themed fiction doesn't come along every day. -----