Publications
Most (but not all) of my publications also can be found at dblp.
-
Adaptive collective responses to local stimuli in anonymous dynamic networks.
Shunhao Oh, Dana Randall, Andréa W. Rich.
SAND 6:1-6:23, 2023.
Colloidal robotics.
A.T. Liu, M. Hempel, J.F. Yang, A.M. Brooks, A. Pervan, V.B. Koman, G. Zhang, D. Kozawa, S. Yang, D.I. Goldman, M.Z. Miskin, A.W. Richa, D. Randall, T.D. Murphey, T. Palacios, M.S. Strano.
Nature Materials, 1453-1462, 2023.
- Mixing times of Markov chains for self-organizing lists and biased permutations.
P. Bhakta, S. Miracle, D. Randall and A. Streib. Random Structures and Algorithms, 61: 638-665, 2022.
(An earlier version appeared in the
24th Symposium on Discrete Algorithms (SODA), 2013.)
- Local stochastic algorithms for alignment in self-organizing particle systems.
H. Kedia, S. Oh and D. Randall.
APPROX/RANDOM, 14:1-14:20, 2022.
- Brief Announcement: Foraging in particle systems via self-induced phase changes.
S. Oh, D. Randall, A.W. Richa.
DISC, 51:1-51, 2022.
- Mathematically quantifying gerrymandering and the non-responsiveness of the 2021 Georgia congressional districting plan.
Z. Zhao, C. Hettle, S. Gupta, J. Mattingly, D. Randall, G. Herschlag. EAAMO, 2022.
- A Heterogeneous Schelling model for wealth disparity and its
effect on segregation. Z. Zhao and D. Randall. EAAMO, 2022.
- Programming active granular matter with mechanically induced phase changes.
S. Li, B. Dutta, S. Cannon, J.J. Daymude, R. Avinery, E. Aydin, A.W. Richa, D.I. Goldman, D. Randall.
Science Advances, 7:17, 2021.
- Sampling biased monotonic surfaces using exponential metrics. S. Greenberg, D. Randall and A. Streib. Combinatorics, Probability and Computing. 29: 672--697, 2020.
- Statistical physics and algorithms. D. Randall. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020.
- Phase coexistence for the hard-core model on D^2.
A. Blanca, Y. Chen, D.J. Galvin, D. Randall, P. Tetali. Comb. Probab. Comput. 28(1): 1-22, 2019.
- A local stochastic algorithm for separation in heterogeneous self-organizing particle systems. S. Cannon, J. Daymude, C. Gokmen, D. Randall, and A. Richa.
International Conference on Randomness and Computation (RANDOM), 2019.
- Slow mixing of Glauber dynamics for the six-vertex model in the ordered phases. M. Farhbach and D. Randall.
International Conference on Randomness and Computation (RANDOM), 2019.
- Phase coexistence for the hard-core model on Z^2. A. Blanca, Y. Chen, D. Galvin, D. Randall, and P. Tetali, Probability, Combinatorics and ComputingVol. 28, 1-22, 2019.
- Phase transitions in random dyadic tilings and rectangular dissections, S. Cannon, S. Miracle and D. Randall, SIAM J. of Discrete Math Vol. 32 1966-1992, 2018. (An earlier version appeared in the 26th Symposium on Discrete Algorithms (SODA), 2015.)
- Brief announcement: A local stochastic algorithm for separation in heterogreneous self-orgnaizing particle systems. S. Cannon, J. Daymude, C. Gokmen, D. Randall, A. Richa, Principles of Distribued Computing (PODC), 2018.
- Slow convergence of Ising and spin glass models with well-separated frustrated vertices. D. Gillman and D. Randall, Analysis of Algorithms (AofA), 2018.
- Analyzing Boltzmann samplers for Bose-Einstein condensates with Dirichlet generating functions, M. Bernestin, M. Fahrbach and D. Randall,
Meeting on Analytic Algorithmics and Combinatorics (ANALCO), 2018.
- Phototactic supersmarticles, S. Cannon, J.J. Daymude, D.I. Goldman, S. Li, D. Randall, A.W. Richa, W. Savoie and R. Warkentin, 2nd International Symposium on Swarm Behavior and Bio-Inspired Robotics (SWARM), 2017.
- A stochastic approach to shortcut bridging in progrmamable matter, M. Andres Arroyo, S. Cannon, J.J. Daymude, D. Randall and A.W. Richa. 23rd International Conference on DNA Computing an Molecular Programming (DNA), 2017.
- Approximately sampling elements with fixed rank in graded posets, P. Bhakta, B. Cousins, M. Fahrbach and D. Randall. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.
- Algorithms to approximately count and sample conforming colorings of graphs, S. Miracle and D. Randall Discrete Applied Mathematics, 133-149, 2016.
- Sampling and counting 3-orientiations of planar triangulations, S. Miracle, D. Randall, A.P. Streib and P. Tetali. SIAM Journal on Discrete Mathematics, 801--831, 2016.
- A Markov chain algorithm for compression in self-organizing particle systems, S. Cannon, J.J. Daymude, D. Randall and A.W. Richa. ACM Syposium on Principles of Distributed Computing (PODC), 2016.
- Sampling on lattices with free boundary conditions using randomized extensions, S. Cannon and D. Randall. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016.
- Sampling weighted perfect matchings on the square-octangon lattice, P. Bhakta and D. Randall. Meeting on Analytic Algorithmics and Combinatorics (ANALCO), 2016.
- Phase coexistence and torpid mixing in the 3-coloring model on ℤ^d, D. Galvin, J. Kahn, D. Randall and G.B. Sorkin. SIAM Journal on Discrete Mathematics, 1223--1244, 2015.
- Clustering and Mixing Times for Segregation Models on Z^2, P. Bhakta, S. Miracle and D. Randall.
25th Symposium on Discrete Algorithms (SODA), pages 327-340, 2014.
- Phase coexistence and slow mixing for the hard-core model on Z^2.A. Blanca, D. Galvin, D. Randall and P. Tetali.17th Workshop on Randomization and Computation (RANDOM), 2013.
- Algorithms to approximately count and sample conforming colorings of graphs S. Miracle and D. Randall. VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2013
- Mixing times of Markov chains on 3-orientations of planar triangulations. S. Miracle, D. Randall, A. Streib and P. Tetali. 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for hte Analysis of Algorithms (AofA), 2012.
- Clustering in interfering models of binary mixtures. S. Miracle, D. Randall and A. Streib.
15th International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM), 2011.
- Cluster algorithms for discrete models of colloids with bars. S. Miracle, D. Randall and A. Streib.
Proceedings of the Second Workshop on Analytic Algorthmics and
Combinatorics (ANALCO), 2010.
- On the Diaconis-Gangolli Markov Chain for
sampling contingency tables with cell-bounded entries. I. Bezakova, N. Bhatnagar and D. Randall.
Journal of Combinatorial Optimization, 2010.
(Conference version appeared earlier in the 15TH International Computing and Combinatorics Conference
(COCOON), 2009.
- Approximately counting integer flows and cell-bounded
contingency tables.
M. Cryan, M. Dyer and D. Randall.
SIAM Journal on Computing, 39: 2683--2703, 2010.
(Conference version appeared earlier in the 37th Symposium on Theory of Computing (STOC), 2005.)
- Self-assembly and convergence rates of heterogenous reversible growth processes. A. Pascoe and D. Randall.
Foundations of Nanoscience (FNANO), 2009.
- Sampling biased lattice configurations
using exponential metrics. Sam Greenberg, A. Pascoe and D. Randall.
20th Symposium on Discrete Algorithms (SODA), 2009.
- Convergence rates of Markov chains for some
self-assembly and non-saturated Ising models.
S. Greenberg and D. Randall.
Theoretical Computer Science, 410: 1417-1427, 2009.
-
Sampling stable marriages: why spouse-swapping won't work.
N. Bhatnagar, S. Greenberg and D. Randall.
19th Symposium on Discrete Algorithms (SODA), 2008.
-
Slow mixing of Markov chains using fault lines
and fat contours.
S. Greenberg and D. Randall. Algorithmica (online first), 2008.
(An earlier version appeared in
11th International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM), 2007.)
-
Markov chain convergence and the efficiency of
some self-assembly models.
D. Randall.
Foundations of Nanoscience: Self-Assembled Archetectures and Devices (FNANO),
117--125, 2007.
-
Torpid mixing of local Markov chains on 3-colorings
of the discrete torus.
D. Galvin and D. Randall.
18th Symposium on Discrete Algorithms (SODA), 2007.
-
The effect of boundary conditions on mixing
rates of Markov chains.
N. Bhatnagar, S. Greenberg and D. Randall.
10th International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM), 2006.
-
Global connectivity from local geometric constraints
for sensor networks with various wireless footprints.
R. D'Souza, D. Galvin, C. Moore and D. Randall.
Information Processing in Sensor Networks (IPSN), 2006.
-
Disjoint decomposition of Markov chains and sampling circuits in Cayley graphs.
R. Martin and D. Randall.
Combinatorics, Probability and Computing 15: 411-448, 2006.
[pdf, ps.gz]
-
Rapidly mixing Markov chains with applications in computer science
and physics. D. Randall. Computing in Science and Engineering, 2006
-
Random bichromatic matchings N. Bhatnagar, D. Randall, V. Vazirani, E. Vigoda. 7th Latin Amerian Theoretical Informatics Symposium (LATIN), 2006.
-
Slow mixing of Glauber dynamics via
topological obstructions. D. Randall. 17th Symposium on Discrete Algorihtms (SODA), 2006.
(This version corrects an error in the original paper claiming better bounds due to a missing factor of 2 in some equations.)
-
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.
9th International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM)
in Lecture Notes in Computer Science, 3624: 426-435, 2005.
-
Mixing points on an interval.
D. Randall and P. Winkler. In
Second Workshop on Analytic Algorthmics and
Combinatorics (ANALCO), 2005.
-
Torpid mixing of simulated tempering on the Potts model.
N. Bhatnagar and D. Randall.
the 15th ACM/SIAM Symposium on Discrete Algorithms (SODA): 478-487, 2004.
[pdf,
ps.gz]
-
Mixing.
D. Randall.
A tutorial on Markov chains in
the 44th Symposium on Foundations of Computer Science
(FOCS): 4-15, 2003.
[pdf,
ps.gz]
-
Dynamic TCP acknowledgement and other stories about e/(e-1).
A.R. Karlin, C. Kenyon and D. Randall.
Algorithmica 36: 209-224, 2003.
[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.
Random Structures and Algorithms 21: 225-251, 2002.
[pdf,
ps.gz]
-
Markov chain decomposition for convergence rate
analysis.
N. Madras and D. Randall.
Annals of Applied Probability, 12: 581-606, 2002.
[pdf,
ps.gz]
-
Decomposition methods and sampling circuits in the Cartesian lattice.
D. Randall.
Mathematical Foundations of Computer Science (MFCS), in
Lecture Notes in Computer Science
1256: 72-84, 2001. (Invited contribution.)
[pdf,
ps.gz]
-
Counting triangulations and pseudo-triangulations of wheels.
D. Randall, G. Rote, F. Santos and J. Snoeyink.
the 13th Canadian Conference on Computational Geometry
(CCCG): 149-152, 2001.
[pdf]
(Slightly longer version.)
-
Markov chain algorithms for planar lattice structures
M. Luby, D. Randall and A.J. Sinclair.
SIAM Journal on Computing, 31: 167-192, 2001.
[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.
41st Symposium on Foundations of Computer Science (FOCS)
492-502, 2000.
[pdf,
ps.gz]
-
Analyzing Glauber dynamics by comparison
of Markov chains.
D. Randall and P. Tetali.
Journal of Mathematical Physics, 41 : 1598-1615, 2000.
[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.
Journal of Mathematical Physics, 41 : 1570-1584, 2000.
[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.
11th SIAM/ACM Symposium on Discrete Algorithms (SODA), 2000.
[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.
Perplexing Problems in Probability: Festschrift in honor of Harry Kesten,
Birkhauser
(M. Bramson and R. Durrett, editors): 159-173, 1999.
[pdf,
ps.gz]
-
Pfaffian algorithms for sampling routings
on regions with free boundary conditions.
R.A. Martin and D. Randall.
3rd International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM)
in Lecture Notes in Computer Science, 1671: 257-268, 1999.
[pdf,
ps.gz]
-
Sampling spin configurations of an Ising system.
D. Randall and D.B. Wilson.
10th Symposium on Discrete Algorithms (SODA): S959-960, 1999.
[pdf,
ps.gz]
-
Approximating the number of monomer-dimer coverings of a
lattice.
C. Kenyon, D. Randall and A.J. Sinclair.
Journal of Statistical Physics, 83: 637-659, 1996.
[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.
37th Symposium on Foundations of Computer Science (FOCS):
194-203, 1996.
-
Efficient generation of random nonsingular matrices.
D. Randall.
Random Structures and Algorithms , 4: 111-118, 1993.
-
Self-packing of centrally symmetric convex bodies in R^2.
P. Doyle, J.C. Lagarias and D. Randall.
Discrete and Computational Geometry, 8: 171-189, 1992.
-
On the transformations of some graphs.
A.M. Odlyzko and D. Randall.
Complex Systems, 1: 203-209, 1987.
-
Counting in lattices: some combinatorial problems from statistical
mechanics.
Ph. D. Thesis: D. Randall.
International Computer Science Institute (ICSI) Technical Report Number TR-055-94, 1994.
[pdf,
ps.gz]
|