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 ABSTRACT: 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 loads. Joint work with Henry Lin, Christos Amanatidis, Martha Sideri, and Dick Karp.