Sriram Pemmaraju, professor in the Department of Computer Science in the College of Liberal Arts and Sciences, and Sourya Roy, assistant professor in the same department, have received a $999,990 National Science Foundation grant for Distributed Random Sampling. The four-year project runs from Aug. 1, 2026, through July 31, 2030. Pemmaraju will serve as the primary investigator and Roy as the co-principal investigator.

Random sampling is a starting point for many computational tasks. Pemmaraju compares the process to shuffling a deck of cards: A well-shuffled deck produces a sequence without favoring one possible arrangement over another. As sampling problems grow larger and more complex, however, algorithms running on a single machine may not scale efficiently. Pemmaraju and Roy will develop algorithms that distribute that work across multiple cooperating machines.  

The project brings together Pemmaraju’s expertise in distributed computing and Roy’s work in areas including pseudo-randomness, graph expansion, and spectral theory. Their research will focus on designing efficient distributed sampling algorithms while also investigating when such algorithms face fundamental limitations. The work has potential applications in distributed systems, networks, and large-scale machine learning.  

“This grant allows me to learn the latest techniques in random sampling and combine these with my knowledge of distributed computing to design efficient distributed random sampling algorithms,” Pemmaraju said. “I also look forward to collaborating with Sourya Roy and the post-doctoral fellows and graduate students we hope to soon recruit for this project.”  

The project will support graduate students and postdoctoral researchers, and Pemmaraju and Roy plan to incorporate the research into courses and share their work through tutorials, workshops, and publications.