Department of Computer Science Colloquium
Thursday, September 5, 2002, 4:15pm 
Upson Hall B17

Algorithmic Problems Related to the Internet

Christos Papadimitriou
University of California at Berkeley

The Internet is the first computational artifact that was not designed by a single entity, but emerged from the free interaction of many. As a result, the Internet and the worldwide web must be approached as mysterious objects to be studied by observation, experiment, and the development of falsifiable theories, not unlike the cell, the universe, the brain, and the market. Since economic self-interest was an important force behind the Internet's emergence, Mathematical Economics and Game Theory seem relevant to this new field. This talk will survey recent results by the speaker and his co-authors on Internet congestion control, data mining, and the Internet topology.