Events Calendar

CS Colloquium: Barna Saha (University of Massachusetts Amherst) - Efficient Fine-Grained Algorithms

Speaker: Barna Saha, University of Massachusetts Amherst

Talk Title: Efficient Fine-Grained Algorithms

Series: Computer Science Colloquium

Abstract: One of the greatest successes of computational complexity theory is the classification of countless fundamental computational problems into polynomial-time and NP-hard ones, two classes that are often referred to as tractable and intractable, respectively. 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. Over the years, many polynomial-time approximation algorithms were devised as an approach to bypass the NP-hardness obstacle of many discrete optimization problems. This area has developed into a rich field producing many algorithmic ideas and has lead to major advances in computational complexity. So far, however, 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 complexity, and my contributions therein. This will include fundamental problems such as edit distance computation, all-pairs shortest paths, parsing and matrix multiplication. They have applications ranging from genomics to statistical natural language processing, machine learning and optimization. I will show how as a natural byproduct of improved time complexity, one may design algorithms that are highly parallel as well as streaming algorithms with sublinear space complexity. Finally, motivated by core machine learning applications, I will discuss alternative measures of efficiency that may be equally relevant as time complexity.

This lecture satisfies requirements for CSCI 591: Research Colloquium.


Biography: Barna Saha is currently an Assistant Professor in the College of Information & Computer Science at the University of Massachusetts Amherst. She is also a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining UMass in 2014, she was a Research Scientist at AT&T Shannon Laboratories, New Jersey. She spent four wonderful years (2007-2011) at the University of Maryland College Park from where she received her Ph.D. in Computer Science. In Fall 2015, she was at the University of California Berkeley as a Visiting Scholar and as a fellow of the Simons Institute. Her research interests include Theoretical Computer Science, Probabilistic Method & Randomized Algorithms and Large Scale Data Analytics. 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) and Dean's Dissertation Fellowship (2011). She received the best paper award at the Very Large Data Bases Conference (VLDB) 2009 for her work on Probabilistic Databases and was chosen as finalists for best papers at the IEEE Conference on Data Engineering (ICDE) 2012 for developing new techniques to handle low quality data.


Host: David Kempe

Location: Seeley G. Mudd Building (SGM) - 101

Audiences: Everyone Is Invited

Contact: Computer Science Department