Consider a Markov chain on the set 
of 
invertible matrices mod 2, where in each step, two distinct rows 
are chosen uniformly at random, and row 
is added to row 
mod 2. How does the mixing time grow with 
? The best upper bound known is 
and the lower bound is of order 
.
It is known that the mixing time for one column of the matrix is of order 
, and in fact there is cutoff.
R. Rivest asked for the mixing time if only test functions that are computable in polynomial time are allowed.
REFERENCES