University of Massachusetts Amherst computer science researcher Barna Saha has been awarded a five-year, $549,986 faculty early career development (CAREER) grant from the National Science Foundation, the agency’s most prestigious award in support of junior faculty who exemplify the role of teacher-scholars through outstanding research, excellent education and integrating education and research with their institution’s mission.
Among other topics, Saha, an expert in algorithms, will explore one of the oldest problems in computing, the fundamental question of what problems can be solved by computers, and solved in a reasonable amount of time, and which are problems that, “no matter how clever you are, you cannot solve them efficiently,” she explains.
In the latter case, she adds, “approximation algorithms can help. They are a less optimal tool, but very close to optimal is almost as good, in fact perhaps good enough when efficiency is concerned. This is one of the areas I’ll be working on: Can we develop a faster algorithm for some of the very hard problems and if not, can we definitely say there is a computational barrier there? That conclusion is valuable because then people can stop working on that particular problem, and turn to ask different questions.”
Complexity theory, from its inception, used concepts such as “polynomial vs NP-hardness” to classify computational problems into two groups: those that have relatively efficient solutions (polynomial time) and those that do not (NP hard), Saha points out.
She writes, “Over the years, seminal works by researchers charting the landscape of approximability of NP-Hard problems have contributed to a significant growth of this field. However, this crude distinction of algorithmic efficiency, polynomial vs NP-hard, is insufficient when handling today’s large scale of data.”
She intends to seek a “finer-grained design and analysis of algorithms” that will lead to a better understanding of “the extent of speed-up possible especially for high-degree polynomial time problems.” She notes that for now, “except for a few problem-specific innovations, the study of such algorithms is deeply lacking in the literature.”
In using approximation algorithms, one trades quality for speed, Saha says, but even with improved algorithms and alternative strategic approaches to data management, in today’s world of “big data,” it is becoming harder and harder for computers to successfully handle the data deluge.
She will develop “systematic techniques that emphasize on the trade-offs between running time, approximation and randomness and aid in designing low-complexity parallel algorithms which will significantly improve the state of the art.”
Saha also hopes to design new courses for students at CICS, and to work closely with industry for possible adaptation of new methodologies for practical big data management problems.
Before coming to UMass Amherst in 2014, Saha was a research scientist at AT&T Shannon Research Laboratory, which she joined after completing her Ph.D. in computer science at the University of Maryland, College Park in 2011. She is also a recipient of the NSF CISE Research Initiation Initiative award for developing fast algorithms for dynamic programming. This led to her solving several long-standing open questions and opened new directions to be pursued in her CAREER proposal.
