Every year the Achievement Rewards for College Scientists (ARCS) program awards exceptional doctoral students who demonstrate past achievement and promise of making vital contributions to science and technology. This year, Georgia Institute of Technology’s School of Computer Science has two ARCS Scholar award winners: Matthew Fahrbach and Samantha Petti.

Fahrbach studies Markov chain Monte Carlo algorithms, which are widely used across science and engineering to sample from intricate probability distributions. In particular, he focuses on random walk algorithms that sample from Boltzmann distributions because of their connections with statistical physics and machine learning.

“Theory allows us to prove performance guarantees and ensure algorithms behave the way we hope they will. This is especially important for randomized and approximation algorithms,” said Fahrbach, a third-year SCS Ph.D. student advised by Professor Dana Randall.

“Matthew is an excellent mathematician and a very strong programmer who has won competitions for both,” Randall said. “The combination gives him a unique perspective for solving problems with a keen eye and talent for the spectrum from theory to practice”                                                                  

Petti’s research focuses on finding a simple, efficient way to model large networks. These networks include everything from connections in the brain to Facebook friendships, but they are often too extensive to effectively test an algorithm.

To overcome this hurdle, she has developed a new mathematical framework for producing a smaller sample network based on the larger network. This can then be extrapolated to develop an algorithm for the larger network. Although Petti is a third-year mathematics Ph.D. student, SCS Professor Santosh Vempala advises her work in Algorithms, Combinatorics and Optimization (ACO).

“It has been most rewarding to work with Samantha Petti, who is amazingly talented,” Vempala said. “Her work has the potential to bridge the fundamental regularity theorem of Szemeredi (for dense graphs) with well-known models of real-world networks (Watts-Strogatz and Barabasi-Albert).”

Both students look forward to the additional $7,500 in funding and the ability to share their research in the academic community.

“This award gives me more flexibility to travel to conferences and workshops where I can present my work and collaborate with other researchers in person,” Fahrbach said.