*
Atlanta, GA | Posted:
September 24, 2009 *

The American Mathematical Society has chosen Dana Randall, Professor in the College of Computing and Adjunct Professor in the School of Mathematics, to deliver the 2009 Arnold Ross Lecture. She will give her lecture, entitled Domino Tilings of the Chessboard: An Introduction to Sampling and Counting, on October 29, 2009 at the National Science Center/Fort Discovery in Augusta.

The AMS established this annual lecture series for talented high school students in 1993, in honor of Arnold Ross (1906-2002), a mathematician and educator who taught at several universities, including Cal Tech, Saint Louis University, Notre Dame, Ohio State, and the University of Chicago. In 1957, while at Notre Dame, he founded the Ross Mathematics Program, a multi-level summer program for gifted high school students talented in mathematics, and this program has been offered every summer since then. The program was moved to Ohio State in 1964 and is currently sponsored jointly by Ohio State and the Clay Mathematics Institute. Previous Ross lecturers include Curtis McMullen and Barry Mazur of Harvard and Kenneth Ribet and Elwyn Berlekamp of the University of California at Berkeley.

Dr. Randall earned her Ph.D. in Computer Science from the University of California at Berkeley in 1994. After postdoctoral appointments at the Institute for Advanced Study and the DIMACS Center at Princeton University, she joined the Georgia Tech faculty in 1996 with a joint appointment in the School of Mathematics and the College of Computing. She has received a Sloan Fellowship, a National Science Foundation Career Award, and the College of Computing's "Gus" Baird Teaching Award and Outstanding Senior Faculty Research Award. Last year she was appointed a lifetime National Associate of the National Academies.

Her research is truly interdisciplinary, blending computer science, discrete mathematics, and statistical physics to construct counting and sampling algorithms that run in polynomial time, and have provable performance guarantees. Many of these algorithms use Markov chains that perform random walks on configurations in a large state space, much like shuffling a deck of cards. The goal is to design algorithms so that samples can be chosen from very close to the stationary distribution after a relatively small number of steps of the random walk.

Many of the problems she works on are motivated by statistical physics, although they are equally familiar in mathematics under different guises. These include the dimer model (perfect matchings), the hard-core model (proper colorings), and lattice gas models (independent sets).

In each case, the Gibbs (or Boltzmann) distribution over the set of configurations is parameterized by temperature, and we are interested in sampling at various settings of this parameter since this allows us to infer many thermodynamic properties of the underlying system. In many cases, Randall and her colleagues have shown that the most natural algorithms are efficient at sufficiently high temperatures, but prohibitively slow at low temperatures, echoing phase transitions that exist in the underlying physical systems themselves.

While potentially discouraging, in fact this realization has shaped the design of more complicated algorithms, and has led to some surprising algorithms that are provably polynomial time, even at low temperatures. An example is the Ising model, a simple model for ferromagnetism. The natural sampling algorithm is slow at low temperatures. Randall and her colleague David Wilson designed an algorithm that allows samples to be drawn from the Gibbs distribution at any temperature, and this remains the only efficient sampling algorithm for the model. Like much of Randall’s research, this result comes from simultaneously viewing the problem through the combined lenses of computer science, mathematics and physics.

She has supervised several Ph. D. students, including current ACO students Sarah Miracle and Amanda Pascoe. Lately all of her time outside of mathematics is spent with her children, Cayla, 2, and Jamie, 1.