Conference paper
The minimum latency problem
Avrim Blum, Prasad Chalasani, et al.
STOC 1994
We present an upper bound O(n2) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process.
Avrim Blum, Prasad Chalasani, et al.
STOC 1994
Don Coppersmith, Madhu Sudan
STOC 2003
Inder S. Gopal, Don Coppersmith, et al.
IEEE TC
Nikhil Bansal, Danny Z. Chen, et al.
Algorithmica (New York)