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.