Personal tools
You are here: Home Events Milner Lectures 2001 Milner Lecture

2001 Milner Lecture

Algorithmic Problems Related to the Internet


Christos Papadimitriou, University of California, Berkeley


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.



Document Actions