🚀 go-pugleaf

           Department of Computer Science, University of Toronto
         (SF = Sandford Fleming Building, 10 King's College Road)

       -------------------------------------------------------------

                                  THEORY
              SF1105, at 3:00 p.m., Thursday 19 November 1992

                           Professor Anne Condon
                    University of Wisconsin at Madison

                    " Random Walks on Colored Graphs "

How long can it take to cover an n node graph, if edges are followed at
random?  This and related problems have been studied in depth both for both
directed and undirected graphs.

In this talk, we modify the set-up: Suppose the graph has edges of
different colors, and a sequence of colors, which is fixed in advance,
specifies which color edge is to be followed at each step.  Suppose that on
any sequence of colors, the graph can still be covered with probability 1.
Then, how long can it take to cover an n-node graph, if an adversary
chooses the sequence which maximizes the cover time?

We will present new results on the expected cover times of undirected
graphs with colored edges. For example, we have exponential upper and lower
bounds on the expected cover time of undirected graphs with two colors, and
double exponential upper and lower bounds for graphs with three or more
colors.

One motivation for studying such questions on graphs with colored edges is
the close connection between colored graphs and space bounded interactive
proof systems.  Also, our work introduces a complexity theoretic
perspective to well-studied questions on time-varying Markov chains.

This is joint work with Diane Hernek.