Barna Saha

Director of the National NSF TRIPODS Institute for Emerging CORE Methods in Data Science (EnCORE)

The Harry E. Gruber Endowed Chair Professor of Computer Science and Information Technologies, Associate Professor, University of California San Diego

Department of Computer Science & Engineering, and Halıcıoğlu Data Science Institute

Previously, I was a tenured Associate Professor at the University of California Berkeley, and even before that on the faculty of Computer Science at UMass Amherst, and as a Senior Research Scientist at the AT&T Shannon Research Laboratory. I am also an Affiliate faculty of the Simons Institute for the Theory of Computing at UC Berkeley.

Email: barnas (at) ucsd (dot) edu

Research Interests: Theoretical Computer Science, Algorithm Design & Analysis, Probabilistic Method and Large Scale Data Analytics.

Selected Awards.

Recent Publications. (For a full list see DBLP)

  • Weighted Edit Distance Computation: Strings, Trees and Dyck, Debarati Das, Jacob Gilbert , MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, STOC 2023
  • An Algorithmic Bridge Between Hamming and Levenshtein Distances, Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha, ITCS 2023
  • Approximating LCS and Alignment Distance over Multiple Sequences, Debarati Das, Barna Saha, APPROX-RANDOM 2022.
  • Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal, Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha, FOCS 2022
  • Õ(n + poly(k))-time Algorithm for Distance k Tree Edit Distance, Debarati Das, Jacob Gilbert , MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh, FOCS 2022
  • Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding, Debarati Das, Tomasz Kociumaka, Barna Saha, ICALP 2022
  • Hierarchical Entity Resolution using an Oracle, Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava, SIGMOD  2022
  • The Complexity of Average-Case Dynamic Subgraph Counting, Monika Henzinger, Andrea Lincoln, Barna Saha, SODA 2022
  • How Compression and Approximation Affect Efficiency in String Distance Measures, Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha, SODA 2022
  • An Upper Bound and Linear-Space Queries on the LZ-End Parsing, Dominik Kempa, Barna Saha, SODA 2022
  • How to Design Robust Algorithms using Noisy Comparison Oracle, Raghavendra Addanki, Sainyam Galhotra, Barna Saha, PVLDB 2021
  • Blocking for Effective Entity Resolution, Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava: Demo SIGMOD 2021
  • Efficient and Effective ER with Progressive Blocking, Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava, VLDB J., 2021
  • Sublinear-Time Algorithms for Computing &Embedding Gap Edit Distance, Tomasz Kociumaka and Barna Saha, FOCS 2020
  • Does Preprocessing help in Fast Sequence Comparisons?, Elazar Goldenberg, Aviad Rubinstein, Barna Saha, STOC 2020
  • Sublinear Algorithms for Gap Edit Distance, Elazar Goldenberg, Robert Krauthgamer, Barna Saha, FOCS 2019
  • Dynamic Set Cover: Improved Algorithms & Lower Bounds, Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi , Barna Saha, STOC 2019
  • Connectivity in Random Annulus Graphs and the Geometric Block Model, Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha, RANDOM 2019
  • Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost, Barna Saha, Sanjay Subramanian, ESA 2019, Track B.
  • Paper Matching with Local Fairness Constraints, Ari Kobren, Barna Saha, Andrew McCallum, KDD 2019. Oral Presentation.
  • Min-Max Correlation Clustering via MultiCut, Saba Ahmadi, Samir Khuller, Barna Saha, IPCO 2019