# Barna Saha

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.

## Education and career

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.

## Research

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 and predicting RNA structure.

### Selected publications

| A. | Khuller, Samir; Saha, Barna (2009), "On finding dense subgraphs", in Albers, Susanne; Marchetti-Spaccamela, Alberto; Matias, Yossi; Nikoletseas, Sotiris E.; Thomas, Wolfgang (eds.), Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, Lecture Notes in Computer Science, vol. 5555, Springer, pp. 597–608, CiteSeerX 10.1.1.722.843, doi:10.1007/978-3-642-02927-1_50, ISBN 978-3-642-02926-4 |
| B. | Haeupler, Bernhard; Saha, Barna; Srinivasan, Aravind (2011), "New constructive aspects of the Lovász local lemma", Journal of the ACM, 58 (6): Article 28, arXiv:1001.1231, doi:10.1145/2049697.2049702, MR 2863399, S2CID 1939336 |
| C. | Saha, Barna; Srivastava, Divesh (2014), "Data quality: The other face of Big Data", in Cruz, Isabel F.; Ferrari, Elena; Tao, Yufei; Bertino, Elisa; Trajcevski, Goce (eds.), IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014, IEEE Computer Society, pp. 1294–1297, doi:10.1109/ICDE.2014.6816764, ISBN 978-1-4799-2555-1, S2CID 1674904 |
| D. | Galhotra, Sainyam; Mazumdar, Arya; Pal, Soumyabrata; Saha, Barna (2018), "The geometric block model", in McIlraith, Sheila A.; Weinberger, Kilian Q. (eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, AAAI Press, pp. 2215–2222 |
| E. | Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska (2019), "Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product", SIAM Journal on Computing, 48 (2): 481–512, arXiv:1707.05095, doi:10.1137/17M112720X, MR 3945252, S2CID 155538888 |

## Recognition

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.

## Personal life

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.