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
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:
- Its unprecedented size, diversity, and availability as an information repository;
- its novel nature as a computer system that intertwines a multitude of economic interests in varying degrees of competition; and
- its history as a shared resource architecture that emerged in a remarkably ad hoc yet gloriously successful manner.
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.
| 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".