The current issue of Computer Science Review is devoted to celebrating the research contributions of Papadimitriou . 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”.
 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