[Colloquium] Alan Frieze's talk tomorrow at TTI

[Eric Vigoda]

Alan Frieze (CMU) is talking tomorrow (Thursday)
at TTI at 12:15 PM.  Lunch will be provided.

Title:  Random Walks on Random Graphs

Abstract:
We discuss several results related to the time taken for a random walk to
visit all vertices of a graph, the cover time. We first discuss this in
relation to two classical models of random graphs viz. $G_{n,p}$ and
random $r$-regular graphs. We give quite precise estimates. We then
consider a random walk on a rather simplified model of a "web-graph" and
estimate the proportion of vertices visitied by a "spider". Finally, we
consider the problem of determining the strong-connectivity or otherwise
of a randomly perturbed digrah -- i.e. a smoothed analysis. We show that
while in the worst-case this is an NL-space complete problem, it is
polynomial time solvable with high probability.