# What is the computational complexity of determining the mixing time of a Cayley graph?

Bayer and Diaconis famously proved that a deck of fifty-two cards will be mixed after only seven dovetail shuffles. Numberphile has a nice series of videos of Diaconis explaining the proof.

I suspect that there's some interactive proofs to show the above.

Given a group $$G$$ having order $$O(\exp n)$$ and representation $$\langle S \vert R\rangle$$, consider the Cayley graph $$\Gamma=\Gamma(G,S)$$ on the $$O(\exp n)$$ vertices.

Suppose Merlin tells me that, starting from the identity and choosing generators $$g\in S$$, a random walk on $$\Gamma$$ will converge to the stationary distribution $$\pi$$ rapidly, in time $$t=O(n)$$. But I am suspicious, and I need to be convinced.

Can I challenge Merlin to find a word of length less than or equal to $$t$$ in the group $$G$$ that equals a particular element of $$G$$ of my choosing, such that the word hashes on to a string of my choosing?

Here I have specialized to groups and Cayley graphs, which may be a red herring; any large, well-defined graph with a configuration space having nice enough properties may also be interesting. Also, I haven't formalized mixing time, but I think most reasonable definitions are polynomially related.