As our world becomes increasingly interconnected, the informational landscape that drives decision-making is marked by ever-expanding scale and interdependencies. Leveraging graph structure, we develop computationally efficient alternatives to canonical subroutines that underlie inference in modern machine learning and optimization infrastructure. We discuss two key directions: First, we optimize graph algorithms for learning from distributed data sources, addressing a key challenge in decentralized settings- namely, identifying simple probabilistic rules for organizing nodes to balance sparsity with reliable connectivity. Our results resolve several open problems related to the exact analysis of connectivity properties in a class of random graph models known as random k-out graphs, widely appearing as heuristics for network design in settings with limited trust. Second, we discuss computationally efficient alternatives to parameter learning in probabilistic graphical models. We develop methods that retain the statistical advantage of classical maximum likelihood estimation while significantly cutting computational costs in the context of high dimensional exponential family models. Summing, our work sheds new light on how the interplay between graph structure and performance can be leveraged to push the frontiers of efficient and provably reliable algorithms.
Mansi Sood is a Schmidt Science Fellow at the MIT Laboratory for Information and Decision Systems, hosted by Devavrat Shah. Her research sits at the interface of network science, stochastic modeling, and learning, with the aim of developing inference algorithms for largescale networks that are both practical and provably reliable. Prior to this, she received her Ph.D. in Electrical and Computer Engineering at Carnegie Mellon University (CMU) where she was recognized with the AG Jordan Award for Outstanding Thesis and Community Impact. She completed her joint B.Tech. and M.Tech. at IIT Bombay, where she received Excellence in Research and Mentorship Award from the Department of Electrical Engineering. Her work won a Best Paper Award at the IEEE International Conference on Communications and a Graduation Day Award in Information Theory and Applications. She has been twice recognized as an EECS Rising Star. For her contributions to outreach and mentorship, she has been honored with an Unsung Hero Award at CMU and the Advanced Graduate Ambassadorship of the Institute for Advanced Study (IAS), Princeton.