Dana Randall's Publications

Dana Randall

Home Publications Recent Activities Lecture Notes Talks Short C.V.

Publications

Convergence rates of Markov chains for some self-assembly and non-saturated Ising models. S. Greenberg and D. Randall (2008). To appear in Theoretical Computer Science.

Sampling stable marriages: why spouse-swapping won't work. N. Bhatnagar, S. Greenberg and D. Randall (2008). SODA 2008 .

Slow mixing of Markov chains using fault lines and fat contours. S. Greenberg and D. Randall (2007). RANDOM 2007.

Markov chain convergence and the efficiency of some self-assembly models. D. Randall (2007). Foundations of Nanoscience: Self-Assembled Archetectures and Devices, 117--125, 2007.

Torpid mixing of local Markov chains on 3-colorings of the discrete torus. D. Galvin and D. Randall (2007). SODA 2007.

The effect of boundary conditions on mixing rates of Markov chains. N. Bhatnagar, S. Greenberg and D. Randall (2006). 10th International Workshop on Randomization and Approximation Techniques in Computer Science (Random).

Global connectivity from local geometric constraints for sensor networks with various wireless footprints. R. D'Souza, D. Galvin, C. Moore and D. Randall (2006). Information Processing in Sensor Networks (IPSN).

Disjoint decomposition of Markov chains and sampling circuits in Cayley graphs. R. Martin and D. Randall (2006). Combinatorics, Probability and Computing 15: 411-448. [pdf, ps.gz]

Rapidly mixing Markov chains with applications in computer science and physics. D. Randall (2006). Computing in Science and Engineering.

Random bichromatic matchings N. Bhatnagar, D. Randall, V. Vazirani, E. Vigoda (2006). LATIN 2006.

Slow mixing of Glauber dynamics via topological obstructions. D. Randall (2006). SODA 2006.

Book review of "Complexities: Women in Mathematics." Times Higher Education Supplement, September 2, 2005. [doc]

Mixing points on a circle. D. Randall and P. Winkler (2005). 9th International Workshop on Randomization and Approximation Techniques in Computer Science (Random '05) in Lecture Notes in Computer Science, 3624: 426-435.

Approximately counting integer flows and cell-bounded contingency tables. M. Cryan, M. Dyer and D. Randall (2005). 37th Symposium on Theory of Computing (STOC): 413-422.

Mixing points on an interval. D. Randall and P. Winkler (2005). In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorthmics and Combinatorics (ALENEX/ANALCO).

Torpid mixing of simulated tempering on the Potts model. N. Bhatnagar and D. Randall (2004). the 15th ACM/SIAM Symposium on Discrete Algorithms (SODA) : 478-487, 2004. [pdf, ps.gz]

Mixing. D. Randall (2003). A tutorial on Markov chains in the 44th Symposium on Foundations of Computer Science (FOCS) : 4-15. [pdf, ps.gz]

Dynamic TCP acknowledgement and other stories about e/(e-1). A.R. Karlin, C. Kenyon and D. Randall (2003). Algorithmica 36: 209-224. [pdf, ps.gz] (Earlier conference version appeared in the 33rd Symposium on Theory of Computing (STOC): 502-509, 2001.)

Random dyadic tilings of the unit square. S. Janson, D. Randall and J. Spencer (2002). Random Structures and Algorithms 21: 225-251. [pdf, ps.gz]

Markov chain decomposition for convergence rate analysis. N. Madras and D. Randall (2002). Annals of Applied Probability, 12: 581-606. [pdf, ps.gz]

Decomposition methods and sampling circuits in the Cartesian lattice. D. Randall (2001). Mathematical Foundations of Computer Science (MFCS), in Lecture Notes in Computer Science 1256: 72-84. (Invited contribution.) [pdf, ps.gz]

Counting triangulations and pseudo-triangulations of wheels. D. Randall, G. Rote, F. Santos and J. Snoeyink (2001). the 13th Canadian Conference on Computational Geometry (CCCG): 149-152. [pdf] (Slightly longer version.)

Markov chain algorithms for planar lattice structures M. Luby, D. Randall and A.J. Sinclair (2001). SIAM Journal on Computing, 31: 167-192. [pdf, ps.gz] (The conference version appeared in the 36th Symposium on Foundations of Computer Science (FOCS) : 150-159, 1995. )

Sampling adsorbing staircase walks using a new Markov chain decomposition method. R.A. Martin and D. Randall (2000). 41st Symposium on Foundations of Computer Science (FOCS) 492-502. [pdf, ps.gz]

Analyzing Glauber dynamics by comparison of Markov chains. D. Randall and P. Tetali (2000). Journal of Mathematical Physics, 41 : 1598-1615. [pdf, ps.gz] (The conference version appeared in Latin American Theoretical Informatics (LATIN) in Lecture Notes in Computer Science 1380: 392-304, 1998.)

Self-testing algorithms for self-avoiding walks. D. Randall and A.J. Sinclair (2000). Journal of Mathematical Physics, 41 : 1570-1584. [pdf, ps.gz/a>] (The conference version ''Testable algorithms for self-avoiding walks'' appeared in the 5th ACM/SIAM Symposium on Discrete Algorithms (SODA) : 593-602, 1994.)

Random three-dimensional tilings of Aztec octahedra and tetrahedra: An extension of domino tilings. D. Randall and G. Yngve (2000). 11th SIAM/ACM Symposium on Discrete Algorithms (SODA). [pdf, ps.gz] (This file is very long! Try the shorter version for a smaller file with some pictures omitted.)

The Van den Berg-Kesten-Reimer inequality. C. Borgs, J.T. Chayes and D. Randall (1999). Perplexing Problems in Probability: Festschrift in honor of Harry Kesten, Birkhauser (M. Bramson and R. Durrett, editors): 159-173. [pdf, ps.gz]

Pfaffian algorithms for sampling routings on regions with free boundary conditions. R.A. Martin and D. Randall (1999). 3rd International Workshop on Randomization and Approximation Techniques in Computer Science in Lecture Notes in Computer Science, 1671: 257-268. [pdf, ps.gz]

Sampling spin configurations of an Ising system. D. Randall and D.B. Wilson (1999). 10th Symposium on Discrete Algorithms (SODA): S959-960. [pdf, ps.gz]

Approximating the number of monomer-dimer coverings of a lattice. C. Kenyon, D. Randall and A.J. Sinclair (1996). Journal of Statistical Physics, 83: 637-659. [pdf, ps.gz] (The conference version appeared in the 25th Sympsium on Theoretical Computer Science (STOC), 1993.)

Factoring Markov chains to bound mixing rates. N. Madras and D. Randall (1996). 37th Symposium on Foundations of Computer Science (FOCS) : 194-203.

Efficient generation of random nonsingular matrices. D. Randall (1993). Random Structures and Algorithms , 4: 111-118.

Self-packing of centrally symmetric convex bodies in R^2. P. Doyle, J.C. Lagarias and D. Randall (1992). Discrete and Computational Geometry, 8: 171-189.

On the transformations of some graphs. A.M. Odlyzko and D. Randall, 1987. Complex Systems, 1: 203-209.

Counting in lattices: some combinatorial problems from statistical mechanics. Ph. D. Thesis: D. Randall (1994). International Computer Science Institute (ICSI) Technical Report Number TR-055-94. [pdf, ps.gz]