Randomized Broadcast and Possible Connection to other Models

Опубликовано 17 августа 2016, 0:45

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.