Randomized Broadcast and Possible Connection to other Models

February 9, 2011
Alexandre Stauffer | CS Dept

We consider the so-called push algorithm, where initially there is only one informed node and, at each time step, each informed node chooses a neighbor independently and uniformly at random and informs it.
In this talk, I will survey my results for the runtime of this algorithm and will mention some yet-to-be-studied connections to other problems, such as cover time of random walks, percolation and sparsifiers.
Time permitting, I will briefly mention my results on percolation on moving graphs and give some open problems.

Speaker Details

Alexandre Stauffer is a graduate student in the department of Computer Science at UC Berkeley. His research centers on probabilistic models for mobile networks. He is currently an intern with the Theory group at MSR.