- About the College
- Future Students
- Current Students
HomeRandomness Hits Big
Four College of Computing professors (and a fifth outside Georgia Tech) will share a $1.08 million grant from the National Science Foundation with the goal of discovering how randomized algorithms can yield solutions to some of the most vexing problems in science and engineering.
All the researchers are affiliated with the Algorithms and Randomness Center (ARC) & ThinkTank, and ARC Director Santosh Vempala, Distinguished Professor of Computer Science, is principal investigator. Vempala’s co-PIs include fellow CS professors Dana Randall and Eric Vigoda, as well as Prasad Tetali, who has a joint appointment with mathematics. Professor Daniel Stefankovic of the University of Rochester also is named in the award.
“Randomness is a great tool for computer science broadly and for understanding the power of computation,” says Santosh Vempala. “We use random bits to make algorithms stronger and faster—in cryptography, for instance—but it has other surprising applications, as well.”
Awarded in September, the grant funds a project titled “Random Processes and Randomized Algorithms.” It is one of just two large NSF awards in CS theory in 2009, and it shows that while one answer to complex problems might be randomness, increased research interest in the area is anything but chance.
The concept behind a randomized algorithm is straightforward enough: It introduces randomness into computational processes, offering the potential to solve problems in much less time than with conventional algorithms (or, indeed, solve them at all, as some problems that can be solved with a high degree of certainty by using randomness are considered unsolvable with more deterministic methods). The ARC grant focuses on one kind of randomized process: the Markov Chain, and particularly the Markov Chain Monte Carlo.
Markov Chains are used in many fields for sampling and to compute probabilities. One example involves card shuffling. Take a brand-new, ordered deck of cards, and pick a shuffling method—it could be a standard shuffle in which two halves of the deck are mixed together, or simply taking one card and inserting it elsewhere in the deck, over and over. This process constitutes a Markov Chain, and a basic question is how many shuffles are needed to sufficiently randomize the deck (that is, to have an equal chance of arriving at any of the exponentially many possible orderings of the cards).
Where the “Monte Carlo” comes in is by using the Markov Chain information to start making predictions. It’s no accident that the process is named after one of the world’s best-known gambling destinations, as randomness itself is a game of chance, and the payoff can be measured in billions of computations saved. The ARC grant will support research meant to tilt the odds in scientists’ favor.
Applying Markov Chains to problems in more and more fields
“[In a given problem] the input may be one that forces you into a long computational path,” Vempala says. “But if you use randomness to hedge your bets and make progress at the same time, it’s not possible for any single [wrong path] to cost you as much. In algorithms, we try to prove this works, no matter the input.”
The researchers bring together expertise in various aspects of Markov Chains, including interactions with other areas of CS, statistical physics, biology and mathematics. They will work together to study the effectiveness of the Markov Chain Monte Carlo method in dealing with data sets of different sizes (sometimes massively different) and across many fields of application.
“For example, we’re finding that with a lot of models in physics, the physical properties of the models have a larger impact on algorithms’ effectiveness than we previously knew,” Randall says. “It’s about developing our intuition so that we understand what’s going on with these algorithms, but then taking the steps necessary to make that intuition rigorous. Which could be years of work.”
“Pairs of us have collaborated before,” Tetali says, “but what’s exciting about this grant is it gives us an official excuse to come together and work on this.”
According to Vempala, the grant will allow ARC to expand its fellowship program (it currently provides 50 percent funding for eight to 10 graduate research assistants per year), as well as bring guest speakers and visitors to campus.
For more information about ARC, visit the center’s website.