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 HREF="http://www.ddj.com/architect/208807268">
   A Conversation with Christos Papadimitriou</A>,
a short interview in the August 2008 of
<A HREF="http://www.ddj.com/">
   Dr. Dobb's Journal</A>.
I first learned of Papadimitriou from a textbook of
his that we used in one of my earliest graduate course,
<A HREF="http://portal.acm.org/citation.cfm?id=549820">
   Elements of the Theory of Computation</A>.
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 HREF="http://www.imdb.com/title/tt0268978/">
   A Beautiful Mind</A>?)
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 <EM>we didn't design</EM>.  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
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-12.html#e2007-12-13T14_47_27.htm">
   communication</A>,
where my
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2008-05.html#e2008-05-03T22_10_00.htm">
   CS grad student</A>
Sergei Golitsinski is taking his research.  The
interviewer quoted net pioneer
<A HREF="http://en.wikiquote.org/wiki/John_Gilmore">
   John Gilmore</A>
in the same arena: "The Net interprets censorship as
damage and routes around it."  This leads to open
questions about
<A HREF="http://www.americanscientist.org/issues/id.3455,y.0,no.,content.true,page.1,css.print/issue.aspx">
   how rumors spread</A>,
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,
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-02.html#e2007-02-08T18_23_50.htm">
   open-source software packages</A>,
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,
<A HREF="http://mitpress.mit.edu/catalog/item/default.asp?tid=9910&ttype=2">
   Turing</A>.
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,

<BLOCKQUOTE><EM>
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.
</EM></BLOCKQUOTE>

Powerful testimony, and the chance to read CS-themed
fiction doesn't come along every day.
-----