TIME: 1:30-2:20 pm,  April 24, 2007

PLACE: CSE 691 (Gates Commons)

TITLE: Linked Decompositions of Networks and Polya Urns with Choice

SPEAKER: Christos Papadimitriou
         UC Berkeley

We propose a novel graph decomposition that enables a scalable form of
internet routing with roughly sqrt(n) memory and logarithmic delay.
Subnetworks are required to be small and with small diameter, no three
of them to overlap, but any two of them to do so. Our main result is
that several popular models of "internet-like graphs", most importantly
the preferential attachment one proposed by Albert and Barabasi, have
such decompositions almost surely; experiments show that so does the
real internet. Part of our analysis involves a variant of the Polya urn
model in which we have a choice between two or more urns; in contrast to
the traditional polya urn model, this twist results in very balanced

Joint work with Henry Lin, Christos Amanatidis, Martha Sideri, and Dick Karp.