Conference paper
Random MAX SAT, random MAX CUT, and their phase transitions
Don Coppersmith, David Gamarnik, et al.
SODA 1998
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.
Don Coppersmith, David Gamarnik, et al.
SODA 1998
Roy L. Adler, Don Coppersmith, et al.
IEEE Trans. Inf. Theory
Don Coppersmith
Linear Algebra and Its Applications
Don Coppersmith, Michael Elkin
SIAM Journal on Discrete Mathematics