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, 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: My research interests span theoretical computer science specifically algorithm design and fine-grained complexity. Here are some examples of recent questions that I am exploring:

  1. How do we design fast algorithms when the date is changing?
  2. How do we improve complexity of classical problems like edit distance and all pairs shortest paths?
  3. How do we improve efficiency of training and inference of popular AI models?

Selected Awards.

Recent Publications. (For a full list see DBLP)

  • The I/O Complexity of Attention, or How Optimal is Flash Attention?, Barna Saha, Christopher Ye
  • On the Complexity of Algorithms with Predictions for Dynamic Graph Problems, Monika Henzinger, Barna Saha, Martin Seybold, Christopher Ye, ITCS 2024
  • Faster Approximate All Pairs Shortest Paths, Barna Saha, Christopher Ye, SODA 2024
  • Approximating Edit Distance in the Fully Dynamic Model, Tomasz Kociumaka, Anish Mukherlee, Barna Saha, FOCS 2023
  • 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