The second annual Kanellakis Memorial Lecture was presented on December 4 by Prof. Christos Papadimitriou of the University of California, Berkeley. This lecture series is in memory of Paris Kanellakis, a prominent computer scientist and Brown faculty member who died with his family in an airplane crash in December 1995.
Papadimitriou, a major figure in computer science, was Kanellakis's thesis advisor at MIT. His lecture, on "Algorithmic Problems in the Internet," discussed how the Internet, and particularly the World Wide Web, has influenced research in theoretical computer science (TCS). He began by stating that the early goals of such research (through 2000) were to "develop a productive mathematical understanding of the capabilities and limitations of the von Neumann computer and its software (the dominant and most novel computational artifacts of that time)." The mathematical tools utilized were combinatorics and logic. He then asked the question, "What should the goals of TCS be today? (And what mathematical tools will be handy?)" Turning things around, he then argued that, because the Internet is so important to today's world and is yet, in many areas, so poorly understood, a "foundational understanding" is "urgently needed."
He went on to discuss three areas, all of which are interesting theoretical problems whose solutions contribute a great deal to our understanding of the Internet and the Web. The first was the use of game theory for routing. He showed, using what he called "inverse game theory," that routing algorithms can be designed that both encourage ISPs to charge fairly and produce reasonable routes through the Internet.
The second area involved finding "random" documents in the web. How does one do this? He showed that by taking a suitably defined random walk through Web links, after 100 steps one could consider oneself "lost" and thereafore at a random Web page. By applying this idea experimentally, he and his students suggest that about 49% of the Web consists of .com domains and 7% of .edu domains.
Finally, he considered the issue of distributions of Web-related things. Such distributions are not normal but appear to have "heavy tails," i.e., are Zipf distributions. For example, he looked at the in-degrees of Web pages and showed that it indeed follows a power-law distribution.
Christos ended his talk by expressing his belief that Paris, a person of broad intellectual pursuits who loved to tackle hard problems, would have enjoyed working on this sort of problem.
A reception with the usual fine food and drink followed the lecture. We were especially pleased to have with us, in addition to the past and present Brown recipients of Kanellakis Fellowships, the holders of this year's Kanellakis fellowships at MIT as well.
