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]
|