Randomized Broadcast and Possible Connection to other Models

  • 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.

    • Portrait of Alexandre Stauffer

      Alexandre Stauffer

    • Portrait of Jeff Running

      Jeff Running

Watch Next