BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Exploring graphs using parallel rotor walks  - Dominik Pajak (Univ
 ersity of Cambridge)
DTSTART:20141121T140000Z
DTEND:20141121T150000Z
UID:TALK56248@talks.cam.ac.uk
CONTACT:Dr Thomas Sauerwald
DESCRIPTION:The most natural deterministic analogue of the random walk in 
 graphs is a process in which walkers are propagated by each node to its ne
 ighbours in a round-robin fashion. Such process\, called the rotor-router 
 has applications for example in load balancing and rumor spreading. In thi
 s talk we will study the speed-up of k-agent rotor-router system with resp
 ect to the cover time of a single walk.\n\nWe will completely resolve the 
 question of the possible range of speed-ups\, showing that its value is be
 tween Θ(log k) and Θ(k)\, for any graph. Both of these bounds are tight.
  Thus\, the proven range of speed-up for the rotor-router corresponds prec
 isely to the conjectured range of speed-up for the random walk. We will al
 so study the speed-up on various graph classes like expanders and multidim
 ensional grids.\n\nJoint work with D. Dereniowski\, R. Klasing\, A. Kosows
 ki\, T. Sauerwald\, P. Uznanski. 
LOCATION:Computer Laboratory\, Room FW26
END:VEVENT
END:VCALENDAR