Efficient Fine-grained Algorithms

From its inception, complexity theory through concepts such as NP-Hardness has classified computational problems into those that have relatively efficient solutions versus those that are intractable. Any problem solvable in time polynomial in the input size falls in the first category. However, this crude distinction of algorithmic efficiency is clearly insufficient when handling today's large scale of data. We need a finer-grained design and analysis of algorithms that pinpoints the exact exponent of polynomial running time, and a better understanding of when a speed-up is not possible. While there is a rich history of designing approximation algorithms for NP-hard problems, a similar theory for high polynomial time problems to understand the trade-off between quality and running time is vastly lacking.

In this presentation, I will give you an overview of the newly growing field of fine-grained algorithms, and my contributions therein. This will include fundamental problems such as edit distance computation, all-pairs shortest paths, parsing and matrix multiplication. I will also discuss alternative measures of efficiency which depending on the application may be equally relevant as time complexity.
Barna Saha received her Ph.D. from the University of Maryland College Park, and then spent a couple of years at the AT&T Shannon Labs as a senior researcher before joining UMass Amherst in 2014. Her research interests are in algorithm design and analysis, and large scale data analytics. She particularly likes to work on problems that are tied to core applications but have the potentials to lead to beautiful theory. She is the recipient of NSF CAREER award (2017), Google Faculty Award (2016), Yahoo Academic Career Enhancement Award (2015), Simons-Berkeley Research Fellowship (2015), NSF CRII Award (2015), Dean's Dissertation Fellowship (2011), and the best paper award and finalists for best papers at VLDB 2009 and IEEE ICDE 2012 respectively.