Root Problems

Monday, August 23, 2010


Dana Randall was always good at math. Her teachers were giving her more difficult problems than her classmates as early as the first grade. A native of New York, Randall attended Stuyvesant High School, the highly competitive New York City public high school that specializes in mathematics and science, before going on to earn a bachelor’s degree in mathematics at Harvard.

Randall graduated from the University of California, Berkeley, with a Ph.D. in computer science and held postdoctoral positions at the Institute for Advanced Study and Princeton University before arriving at Georgia Tech in 1996 in a joint position with the College of Computing and the School of Mathematics. Since then she has established an exciting research program in a new field of interdisciplinary work that brings together intuition and technique from multiple fields.

“We are working on a set of problems that have roots in physics, discrete math and computer science. Through an evolutionary process something new is rising out of that convergence of fields,” she says. “The way we are approaching these problems would have been unthinkable 15 years ago.”

Randall, now a professor of computer science, works in the area of randomized algorithms, specifically those using random sampling. Her research in discrete mathematics and theoretical computer science involves designing Markov chain Monte Carlo algorithms for counting and sampling from large sets of combinatorial structures. The goal is to design fast algorithms that guarantee the selection of a uniformly random sample from the large set.

These algorithms are prevalent not only in computing, but in engineering and many other areas of science as well. Markov chains, in particular, have applications in physics, statistics, gambling and the Internet—such as the system used by Google to rank web pages in response to a user search.

“One of the things I love about this area is how you can take a concept from one field and apply it to research in another,” Randall says.

Ellen Zegura, chair of the School of Computer Science, calls Randall a leader in random sampling and a community builder who helps bring together researchers from varied fields.

“Dana brings a tremendous passion to everything she does, from research to teaching to advocating for students,” Zegura says. “She has a gift for clear thinking and conveying complex concepts to a broad audience. Her extraordinary teaching skill and schedule of invited lectures and tutorials are testament to that.”

Randall started teaching in high school, when she captained Stuyvesant’s internationally known Math Team and gave lessons to her teammates and other math enthusiasts in the school. A lover of puzzles, she approaches teaching as a kind of puzzle itself, one that challenges her to find the most effective way to connect and share knowledge.

“Teaching is an opportunity to show someone what’s interesting about something,” she says. “I really enjoy teaching undergraduates who think that a class in algorithms is going to be horrible. I even tell them in the beginning that by the end of the semester they are going to think algorithms are really cool. They never believe me, but it’s often true.”

Randall, who was named a National Associate of the National Academies in early 2009, received an NSF Career Award in 1997 and an Alfred P. Sloan Research Fellowship in 2001. She has been selected to give several prestigious talks including an American Mathematical Society (AMS) invited lecture at the 2002 joint mathematics meeting and the AMS’ annual Arnold Ross Lecture at the National  Science Center/Fort Discovery in Augusta, Ga., in October 2009. She is currently the chair of the program committee of the AMS/SIAM Symposium on Discrete Algorithms.