Barna Saha

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

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

Previously, I was an Associate Professor of IEOR at the University of California Berkeley, and even before that Associate Professor of Computer Science at UMass Amherst, and 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.

  • 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 ConstraintsAri Kobren, Barna Saha, Andrew McCallum, KDD 2019. Oral Presentation.
  • Min-Max Correlation Clustering via MultiCut, Saba Ahmadi, Samir Khuller, Barna Saha, IPCO 2019