Consider a -regular undirected graph. A walk from a vertex is a sequence of edge labels in , which corresponds to a path on the graph that starts at and at step follows the edge labeled by out of the current vertex, where is the ‘s element of the sequence. Random walks (where the edge labels are random) have lots of very useful properties. In particular, with very high probability, a polynomially-long (in the size of the graph) random walk visits each one of the vertices of the graph (i.e. “covers” the graph). There are many ways in which one may try to derandomize a random walk, one of which was introduced by Stephen Cook in the late 70’s and is known as a Universal Traversal Sequence (UTS). This is quite an incredible notion when you think of it: one fixed polynomially long (in ) walk that covers every graph (on vertices). The probabilistic-method shows that a polynommially-long UTS exists. Unfortunately, while almost every walk of the appropriate size is a UTS, we do not know of any explicit one (i.e., any algorithm that produces a polynomially-long UTS). The shortest UTS we know is based on Nisan’s pseudorandom generators that fool small space computations and is long.

As a first post in what may (or may not) turn out to be a new sequence titled “questions we should have solved by now,” lets see how far we can simplify the problem of explicit UTS and still not solve it.  Specifically, what if our graph has a small diameter. For example, expander graphs have logarithmic diameter, which should make the problem much easier shouldn’t it? Well, the shortest UTS for expanders is still the -long one based on Nisan’s generators. Well, if logarithmic diameter doesn’t save us, perhaps constant diameter? How about diameter one? Yes, can we have a UTS for a clique?  You may be thinking – the clique on $n$ vertices is a single graph, how hard can it be to come up with a UTS for a single graph? Turns out that it is not that easy.  The shortest explicit UTS we know for the clique is … wait for it, wait for it … still the -long one based on Nisan’s generators! How come? There is indeed only one clique, but the there can be many possible ways to label the edges of the clique and the UTS should cover the clique for all such labellings.

Of course, we all know how difficult simple-looking problems can really be, but please share with us your favorite problems that “should have been solved by now.”