Randomized Broadcast and Possible Connection to other Models

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=EdS4ObOEEQQ


Duration: 44:11
15 views
0

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.



Other Videos By Microsoft Research


2016-08-16Microsoft Overview: Library & Bing, Pivot Viewer & Silverlight, Office Labs, Xbox / Kinect
2016-08-16Improving the Future by Examining the Past
2016-08-16Symmetry-Aware Predicate Abstraction for Shared-Variable Concurrent Programs
2016-08-16Using Technology the Cherokee Way
2016-08-16Statistical Physics, Interpolation Method and Scaling Limits in Sparse Random Graphs
2016-08-16An Elementary Proof of the Restricted Invertibility Theorem
2016-08-16Personal Space and Automatically Learned Social Networks
2016-08-16Cloud Enabled Mobile Computing - An Introduction. Lecture 3 Location and Context
2016-08-16Cloud Enabled Mobile Computing - An Introduction. Lecture 1 Definitions and Technology
2016-08-16On the Fourier Spectrum of Symmetric Boolean Functions
2016-08-16Randomized Broadcast and Possible Connection to other Models
2016-08-16The Reconstruction Problem on the Tree
2016-08-16Information and Interactive Communication
2016-08-16The Impact of Visualization on Search and Discovery; ScienceCinema; Speech Processing Quaero
2016-08-16Interactive Illustrations; Delivering Interactive 3D Moleculars; Interactive Multimedia Publishing
2016-08-16Semantics of Innovation in Visualization; PivotViewer; Visualization of Ecological Data
2016-08-16Telling Stories in the Cloud; Communications from the Particle Frontier; Video Analytics
2016-08-16On Users' Mental Models of Security Controls
2016-08-16Why Don't Software Developers Use their Tools?
2016-08-16The Mathematics of Side-Channel Attacks
2016-08-16PyPy's Approach to Implementing Dynamic Languages Using a Tracing JIT Compiler


Tags:
microsoft research