Barna Saha is an Indian-American theoretical computer scientist whose research interests include algorithmic applications of the probabilistic method, probabilistic databases, fine-grained complexity, and the analysis of big data. She is an associate professor and Jacobs Faculty Scholar in the Department of Computer Science & Engineering at the University of California, San Diego.
Saha is originally from Siliguri, and grew up intending to follow her mother into a career in chemistry. She was an undergraduate at Jadavpur University, and earned a master's degree at IIT Kanpur in 2006. She completed her Ph.D. in 2011 at the University of Maryland, College Park, with Samir Khuller as her doctoral advisor. Her dissertation was Approximation Algorithms for Resource Allocation.
After completing her doctorate, she became a senior member of the technical research staff at the Shannon Research Laboratory of AT&T Labs. In 2014 she moved to the College of Information and Computer Science at the University of Massachusetts Amherst as an assistant professor. She worked there for five years, earning tenure as an associate professor, and then moved to the University of California, Berkeley, in the Department of Industrial Engineering and Operations Research, before moving again to the University of California, San Diego in 2022.
She is a co-founder of TCS Women, a network for women in theoretical computer science.
Saha's research publications include work on algorithms for finding dense subgraphs, a version of the algorithmic Lovász local lemma for large numbers of random events, data quality, and the stochastic block model for random graph community modeling. She has also collaborated with Virginia Vassilevska Williams and others on the fine-grained complexity of computing edit distance and predicting RNA structure.
In 2019, Saha won the Presidential Early Career Award for Scientists and Engineers, and was named a Sloan Fellow. In 2020, IIT Kanpur gave her their Young Alumnus Award.
Saha is married to Arya Mazumdar, a coding theorist and machine learning researcher who is also a computer science faculty member at the University of California, San Diego.