BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260727T085208Z
UID:Seminar-ACTO/Networks-970@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Othon Michail:MAILTO:Othon.Michail@liverpool.ac.uk
DTSTART:20201209T140000
DTEND:20201209T150000
SUMMARY:ACTO/Networks Series
DESCRIPTION:John Sylvester: Choice and Bias in Random Walks\n\n We consider two types of controlled random walks on graphs.\n\n   In the choice random walk, the controller chooses between two random\n\n   neighbours at each step; in the epsilon-biased random walk the controller\n\n   instead has a small probability at each step of a free choice of neighbour.\n\n   The former was previously studied empirically by Avin and Krishnamachari\n\n   (2008). The latter was introduced for a fixed set of biases by Azar et al.\n\n   (1996), but we extend it to allow biases to depend on the previous walk.\n\n   In particular, we consider finding the problem of finding optimal strategies\n\n   for the controller minimising the expected time to hit a given vertex or visit\n\n   (cover) all vertices. Using a general framework for boosting the probabilities\n\n   of rare events, we show a significant speed up over the simple random\n\n   walk for graphs with good expansion properties. We also establish a complexity\n\n   dichotomy for making optimal choices, which are tractable for hitting times but\n\n   NP-hard for cover times on undirected graphs (and PSPACE-complete for directed graphs).\n\n   This is joint work with Agelos Georgakopoulos, John Haslegrave and Thomas Sauerwald.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=970
LOCATION:
END:VEVENT
END:VCALENDAR