Amin Saberi, Management Science and Engineering Department, Stanford University

The issue of performance scalability is of fundamental importance in complex communications networks. How does congestion scale on the Internet? At what rate do crawlers discover new web pages? In this talk, I will focus on the expansion and spectral gap of a network and show how they help characterize the performance of many algorithms. I use these concepts to answer the above questions in several families of random graphs that model the Internet and WWW. I will also talk about distributed algorithms that can measure, maintain, or improve these metrics on a large-scale decentralized network such as a peer-to-peer network.

Amin Saberi is an Assitant Professor of Management Science and Engineering and affiliated with the Institute for Computational and Mathematical Engineering at Stanford University. He received his BS from Sharif University in 2000 and his PhD from Georgia Institute of Technology in 2004. He also was post-doc in the Theory group at Microsoft Research. He is interested in the design and analysis of efficient algorithms especially in the areas of algorithmic game theory and approximation algorithms. His interests also include modeling, design, and algorithmic analysis of large-scale complex networks such as the Internet, WWW, or peer-to-peer networks.