By any measure or metric, the road from Siliguri, a small town outside Darjeeling, India, to UC San Diego’s Department of Computer Science and Engineering (CSE) is a long one. At one end, the road lacks infrastructure. Education opportunities are limited. At the other, a world-class university buzzes with potential.
For new CSE Associate Professor Barna Saha, that long road from Siliguri to San Diego was inspired by parents who had a “golden dream” for her higher education. The road was traveled with the encouragement of her husband, Arya Mazumdar, an associate professor at UC San Diego’s Halıcıoğlu Data Science Institute (HDSI). Above all, it was paved by Saha’s diligence and intellect and marked by a series of impressive achievements.
Most notably, Saha is a 2019 recipient of the Presidential Early Career Award for Scientists and Engineers (PECASE) – the highest honor bestowed by the United States government to those who show exceptional promise in their chosen fields. That same year, Saha earned the prestigious Sloan Fellowship, and in 2020, she was honored with the Young Alumnus Award from the Indian Institute of Technology Kanpur. She is also a Jacobs Faculty Scholar in UC San Diego's Jacobs School of Engineering.
Prior to joining UC San Diego, Saha was an associate professor in the Department of Industrial Engineering and Operations Research at the University of California Berkeley. She also taught for five years at the University of Massachusetts Amherst as an assistant, and then associate professor of computer science.
Algorithms for a Data-Rich Life
Saha, who joined the CSE faculty in January 2022, is a theoretical computer scientist and mathematician. Like others in the field, Saha investigates the computer’s effectiveness and speed at problem solving and the barriers to optimization. Saha’s innovative approach to these long-standing computing problems is what has garnered recognition for her early research.
“I am designing faster algorithms,” says Saha. “Given that now you have to deal with very large data, traditional algorithm design needs to be revamped. Data is not just massive; it’s very complex. It’s rapidly changing.”
Saha’s research focuses on building a unified theory of fine-grained algorithm design and understanding the true complexity of polynomial time. Saha explains that the old classification system for polynomial time is bifurcated, offering P for efficient and NP for not efficient. According to Saha, these classifications are overly simplistic. She contends that not all the problems under P are efficient.
Finer-grained classification is about understanding the true complexity of algorithms for a particular problem. Saha’s research looks at the structures underlying the data and evaluates the trade-offs between running time, approximation and randomness at the finest level.
“There is always a trade-off. If you want to gain in something, you have to lose in something,” says Saha. “So, the question is: what is the best trade-off possible?”
For many applications, this inevitable trade-off relates to the tenuous relationship between speed and precision. Saha and her collaborators have found significantly faster approximation algorithms for important optimization problems. The trade-off is a loss of precision. For many applications, such as data cleaning and genome comparison, an estimate could be close enough.
“We might not be able to return the exact solution, but we will return a solution within a confidence interval,” says Saha. “With very high probability, the solution will be very close to the optimum.”
Saha illustrates the benefits of speed over precision using a hypothetical example in genome sequencing. If a lab compares two strands – one from a known cancer patient and another from an undiagnosed patient – a fast approximation algorithm that returns 97 out of 100 positions could be more beneficial to the patient than a slower algorithm capable of returning all 100 positions. In this case, the results would be close enough to indicate whether the sample should be cultured further.
A Platform for Women in STEM
Saha’s impact is felt beyond the research lab and classroom. She is passionate about helping other women and minorities succeed in STEM fields. In 2018, Saha co-founded TCS (Theoretical Computer Science) Women. The program breaks down barriers for women pursuing a Ph.D. by offering access to essential resources and building a critical network of support.
TCS Women raises funding for women to attend conferences and has funded 30 to 50 students annually since its inception. The organization also offers TCS Women’s Spotlight Workshops at conferences, providing graduating women from the U.S. and other countries a platform for presenting their research.
“It’s really important that you have somebody who will stand by you,” says Saha. “I think that’s something every student needs irrespective of where they come from.”