Christos Papadimitriou
July 31, 2009, 6:58 pm
Filed under: Uncategorized | Tags: ,

The current issue of Computer Science Review is devoted to celebrating the research contributions of Papadimitriou [1].  The issue contains a nice mix of accolades and ideas.  On the accolades side, I was impressed by the degree to which Papadimitriou has helped create a vibrant theory community in his home country of Greece, which has produced more than its fair share of notable theory researchers.

On the idea side, there are two survey papers of work connected to Papadimitriou that I particularly liked, one by Koutsoupias on the k-server problem and one by Kleinberg and Raghavan on internet structure, network routing and web information.  One of the very first dissertations I ever read was Koutsoupias’ dissertation (done under Papa.), which showed that the work function algorithm for the k-server problem had a competitive ratio of 2k-1, where the previous best known ratio was exponential in k.  This dissertation helped me fall in love with CS theory: beautiful math and ideas, a crisp problem statement, a clear understanding of when progress is made on a problem.  Plus, the entire dissertation is only 41 pages – that’s perhaps the best way to appreciate what a major result it was!

Bonus Papadimitriou link: Check out the following Papa. talk on why “CS is the new math”.

[1] Tip of the hat to journal editor-in-chief and friend Josep Diaz who air-mailed me the current issue of the journal.  A very enjoyable part of my sabbatical last year was spent in Barcelona at UPC working with Josep.

4 Comments so far
Leave a comment

This specific issue was guest edited by
E.Koutsoupias and P. Spirakis.


Comment by josep diaz

[…] Αυγούστου 6, 2009 Via Machinations we learn that the current issue (Volume 3, Issue 2, May 2009) of Computer Science Review is devoted […]

Pingback by A glimpse at Christos H. Papadimitriou « Blogs are like opinions. Everybody has one…

Which Kleinberg and Raghavan paper was the one you liked? They’ve authored quite a few together.

Comment by Bill Mill

The paper by Kleinberg and Raghavan in the issue of this Computer Review was a survey paper (by Kleinberg and Raghavan) of Papadimitirou’s work on internet structure (and why powerlaw degrees might appear so frequently), routing and the web.

Comment by Jared

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: