The 2001 Milner Lecture

Algorithmic Problems Related to the Internet

Christos Papadimitriou

C. Lester Hogan Professor of Computer Science
University of California, Berkeley

4.30pm Wednesday 23 May 2001

(Streaming video)

The Internet has arguably superseded the computer as the most complex cohesive artifact (if you can call it that), and is, quite predictably, the source of a new generation of foundational problems for Theoretical Computer Science. These new theoretical challenges emanate from several novel aspects of the Internet:

In this talk I will survey some recent research (done in collaboration with Joan Feigenbaum, Dick Karp, Elias Koutsoupias, and Scott Shenker) on problems of the two latter kinds.

Picture of Christos Papadimitriou Professor Papadimitriou is known for his foundational work in computational complexity, and has lead the way in applying techniques from theoretical computer science to other fields, including logic, database systems and economics. His work has also made important contributions in optimization, artificial intelligence, game theory, and computational biology.

This is a public lecture, open to all, and will be followed by a reception at 5.30pm in the Talbot Rice Gallery. Please tell Dyane Goodchild if you intend to come to the reception. This is one of a range of events comprising the University of Edinburgh Informatics Jamboree, 23-25 May 2001.

The annual Milner Lecture was founded by a donation from Robin Milner "to keep a live connection between theory and application in computer science".