Barna Saha

4185 Etcheverry Hall
Personal Webpage: 
E-mail: barnas (at) berkeley (dot) edu

Before joining the Berkeley IEOR department, I was an Assistant Professor of Computer Science at the University of Massachusetts Amherst from 2014-2019.  Before UMass, I was a Research Scientist at AT&T Shannon Laboratories, New Jersey. I spent four wonderful years (2007-2011) at the University of Maryland College Park from where I received my Ph.D. in Computer Science. In Fall 2015, I was at the University of California Berkeley as a fellow of the Simons Institute
Research Interests: Theoretical Computer Science, Probabilistic Method & Randomized Algorithms and Large Scale Data Analytics.

Selected Awards:

Sloan Fellowship, 2019
NSF CAREER Award, 2017
NSF CRII Award, 2015
Google Faculty Research Award, 2016
Yahoo Academic Enhancement Award, 2015
Simons Berkeley Research Fellow, 2015

• Theoretical Computer Science,
• Probabilistic Method & Randomized Algorithms and
• Large Scale Data Analytics.

• Dynamic Set Cover: Improved Algorithms & Lower Bounds, Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi , Barna Saha, STOC 2019.
• Fast Space-Efficient Approximations of Language Edit Distance and RNA-Folding: An Amnesic Dynamic Programming Approach Barna Saha, FOCS 2017.
• Clustering via Crowdsourcing, Arya Mazumdar and Barna Saha, arxiv preprint, April 2016. [Newer versions available here and here]
  1. Query Complexity of Clustering with Side Information, NIPS 2017.
  2. Clustering with Noisy Queries, NIPS 2017.
• Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, Karl Bringmann, Fabrizio Grandoni, Barna Saha and Virginia Williams, FOCS 2016. Invited to special issue for selected best papers. Highlights of Algorithms 2017.
• Language Edit Distance & Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms & Connection to Fundamental Graph Problems, Barna Saha, FOCS 2015.
• The Dyck Language Edit Distance Problem in Near-linear Time, Barna Saha, FOCS 2014.
• New Constructive Aspects of the Lovasz Local Lemma, Bernhard Haeupler, Barna Saha and AravindSrinivasan. Journal of ACM 2011. Conference version at FOCS 2010.
• On Repairing Structural Problems in Semi-structured Data, Flip Korn, Barna Saha, Divesh Srivastava and Shanshan Ying. VLDB 2013.
• Discovering Conservation Rules, Lukasz Golab, Howard Karloff, Flip Korn, Barna Saha and Divesh Srivastava.  IEEE Transactions on Knowledge and Data Engineering (TKDE) 2014. Special Issue on the Best Papers of ICDE 2012.
• A Unified Approach to Ranking in Probabilistic Databases, with Jian Li, Barna Saha and Amol Deshpande. The VLDB Journal, 2011.