Barna Saha

ORCID

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 81

Top Venues

University of Maryland, College Park, MD, USA (PHD)

Education History

University of Maryland, College Park, MD, USA

PHD

Publications

Monika Henzinger, Barna Saha, Martin P. Seybold, Christopher Ye
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. ITCS (2024)
Donatella Firmani, Sainyam Galhotra, Barna Saha, Divesh Srivastava
Building Taxonomies with Triplet Queries. SEBD (2024)
Barna Saha, Christopher Ye
The I/O Complexity of Attention, or How Optimal is Flash Attention? CoRR (2024)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC. SPAA (2024)
Barna Saha, Christopher Ye
Faster Approximate All Pairs Shortest Paths. SODA (2024)
Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More. CoRR (2024)
Barna Saha, Christopher Ye
Faster Approximate All Pairs Shortest Paths. CoRR (2023)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Weighted Edit Distance Computation: Strings, Trees, and Dyck. STOC (2023)
Monika Henzinger, Andrea Lincoln, Barna Saha, Martin P. Seybold, Christopher Ye
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. CoRR (2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. ITCS (2023)
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
Approximating Edit Distance in the Fully Dynamic Model. CoRR (2023)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Weighted Edit Distance Computation: Strings, Trees and Dyck. CoRR (2023)
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
Approximating Edit Distance in the Fully Dynamic Model. FOCS (2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. CoRR (2022)
Debarati Das, Tomasz Kociumaka, Barna Saha
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. ICALP (2022)
Debarati Das, Barna Saha
Approximating LCS and Alignment Distance over Multiple Sequences. APPROX/RANDOM (2022)
Monika Henzinger, Andrea Lincoln, Barna Saha
The Complexity of Average-Case Dynamic Subgraph Counting. SODA (2022)
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
How Compression and Approximation Affect Efficiency in String Distance Measures. SODA (2022)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. FOCS (2022)
Dominik Kempa, Barna Saha
An Upper Bound and Linear-Space Queries on the LZ-End Parsing. SODA (2022)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. CoRR (2022)
Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava
Hierarchical Entity Resolution using an Oracle. SIGMOD Conference (2022)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. FOCS (2022)
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha
Community Recovery in the Geometric Block Model. CoRR (2022)
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
How Compression and Approximation Affect Efficiency in String Distance Measures. CoRR (2021)
Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava
Efficient and effective ER with progressive blocking. VLDB J. 30 (4) (2021)
Raghavendra Addanki, Sainyam Galhotra, Barna Saha
How to Design Robust Algorithms using Noisy Comparison Oracle. Proc. VLDB Endow. 14 (10) (2021)
Raghavendra Addanki, Sainyam Galhotra, Barna Saha
How to Design Robust Algorithms using Noisy Comparison Oracle. CoRR (2021)
Monika Henzinger, Andrea Lincoln, Barna Saha
The Complexity of Average-Case Dynamic Subgraph Counting. Electron. Colloquium Comput. Complex. 28 (2021)
Barna Saha
Approximation Algorithms for Large Scale Data Analysis. PODS (2021)
Debarati Das, Barna Saha
Approximating LCS and Alignment Distance over Multiple Sequences. CoRR (2021)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. CoRR (2021)
Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava
BEER: Blocking for Effective Entity Resolution. SIGMOD Conference (2021)
Barna Saha
Sublinear Algorithms for Edit Distance (Invited Talk). MFCS (2021)
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
Does Preprocessing help in Fast Sequence Comparisons? CoRR (2021)
Debarati Das, Tomasz Kociumaka, Barna Saha
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. CoRR (2021)
Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava
Efficient and Effective ER with Progressive Blocking. CoRR (2020)
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
Does preprocessing help in fast sequence comparisons? STOC (2020)
Tomasz Kociumaka, Barna Saha
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. CoRR (2020)
Tomasz Kociumaka, Barna Saha
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. FOCS (2020)
Saba Ahmadi, Sainyam Galhotra, Barna Saha, Roy Schwartz
Fair Correlation Clustering. CoRR (2020)
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
Sublinear Algorithms for Gap Edit Distance. FOCS (2019)
Barna Saha, Sanjay Subramanian
Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. CoRR (2019)
Barna Saha, Sanjay Subramanian
Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. ESA (2019)
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha
Dynamic set cover: improved algorithms and lower bounds. STOC (2019)
Saba Ahmadi, Sainyam Galhotra, Samir Khuller, Barna Saha, Roy Schwartz
Min-Max Correlation Clustering via MultiCut. CoRR (2019)
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
Sublinear Algorithms for Gap Edit Distance. CoRR (2019)
Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava
Crowd-Sourced Entity Resolution with Control Queries. SEBD (2019)
Ari Kobren, Barna Saha, Andrew McCallum
Paper Matching with Local Fairness Constraints. CoRR (2019)
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha
Connectivity of Random Annulus Graphs and the Geometric Block Model. APPROX-RANDOM (2019)
Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. SIAM J. Comput. 48 (2) (2019)
Saba Ahmadi, Samir Khuller, Barna Saha
Min-Max Correlation Clustering via MultiCut. IPCO (2019)
Ari Kobren, Barna Saha, Andrew McCallum
Paper Matching with Local Fairness Constraints. KDD (2019)
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha
The Geometric Block Model. AAAI (2018)
Barna Saha, Aravind Srinivasan
A new approximation technique for resource-allocation problems. Random Struct. Algorithms 52 (4) (2018)
Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang
Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue. ACM Trans. Algorithms 14 (3) (2018)
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha
Connectivity in Random Annulus Graphs and the Geometric Block Model. CoRR (2018)
Donatella Firmani, Sainyam Galhotra, Barna Saha, Divesh Srivastava
Robust Entity Resolution Using a CrowdOracle. IEEE Data Eng. Bull. 41 (2) (2018)
Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava
Robust Entity Resolution using Random Graphs. SIGMOD Conference (2018)
Sainyam Galhotra, Soumyabrata Pal, Arya Mazumdar, Barna Saha
The Geometric Block Model and Applications. Allerton (2018)
Raghavendra Addanki, Barna Saha
Fully Dynamic Set Cover - Improved and Simple. CoRR (2018)
Rajesh Jayaram, Barna Saha
Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!. ICALP (2017)
Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. CoRR (2017)
Arya Mazumdar, Barna Saha
Clustering with Noisy Queries. NIPS (2017)
Arya Mazumdar, Barna Saha
A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution. AAAI (2017)
Arya Mazumdar, Barna Saha
Clustering with Noisy Queries. CoRR (2017)
Arya Mazumdar, Barna Saha
A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution. CoRR (2017)
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha
The Geometric Block Model. CoRR (2017)
Arya Mazumdar, Barna Saha
Query Complexity of Clustering with Side Information. CoRR (2017)
Barna Saha
Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. FOCS (2017)
Arya Mazumdar, Barna Saha
Query Complexity of Clustering with Side Information. NIPS (2017)
Donatella Firmani, Barna Saha, Divesh Srivastava
Online Entity Resolution Using an Oracle. Proc. VLDB Endow. 9 (5) (2016)
Samir Khuller, Barna Saha, Kanthi K. Sarpatwar
New Approximation Results for Resource Replication Problems. Algorithmica 74 (3) (2016)
Arya Mazumdar, Barna Saha
Clustering Via Crowdsourcing. CoRR (2016)
Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. FOCS (2016)
Mohammad Taghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha
-Median. ACM Trans. Algorithms 12 (3) (2016)
Arya Mazumdar, Barna Saha
Clustering with an oracle. Allerton (2016)
Shanshan Ying, Flip Korn, Barna Saha, Divesh Srivastava
TreeScope: Finding Structural Anomalies In Semi-Structured Data. Proc. VLDB Endow. 8 (12) (2015)
Lukasz Golab, Flip Korn, Feng Li, Barna Saha, Divesh Srivastava
Size-Constrained Weighted Set Cover. ICDE (2015)
Barna Saha
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. FOCS (2015)
Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha
Facility Location with Matroid or Knapsack Constraints. Math. Oper. Res. 40 (2) (2015)
Lukasz Golab, Marios Hadjieleftheriou, Howard J. Karloff, Barna Saha
Distributed data placement to minimize communication costs via graph partitioning. SSDBM (2014)
Mohammad Taghi Hajiaghayi, Theodore Johnson, Mohammad Reza Khani, Barna Saha
Hierarchical graph partitioning. SPAA (2014)
Barna Saha
The Dyck Language Edit Distance Problem in Near-Linear Time. FOCS (2014)
Lukasz Golab, Howard J. Karloff, Flip Korn, Barna Saha, Divesh Srivastava
Discovering Conservation Rules. IEEE Trans. Knowl. Data Eng. 26 (6) (2014)
Barna Saha, Divesh Srivastava
Data quality: The other face of Big Data. ICDE (2014)
Barna Saha
Faster Language Edit Distance, Connection to All-pairs Shortest Paths and Related Problems. CoRR (2014)
MohammadTaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha
-Median. SODA (2014)
Seungjoon Lee, Manish Purohit, Barna Saha
Firewall placement in cloud data centers. SoCC (2013)
Flip Korn, Barna Saha, Divesh Srivastava, Shanshan Ying
On Repairing Structural Problems In Semi-structured Data. Proc. VLDB Endow. 6 (9) (2013)
Barna Saha
Efficiently Computing Edit Distance to Dyck Language. CoRR (2013)
Mohammad Taghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median. CoRR (2013)
Lukasz Golab, Marios Hadjieleftheriou, Howard J. Karloff, Barna Saha
Distributed Data Placement via Graph Partitioning. CoRR (2013)
Barna Saha
Renting a Cloud. FSTTCS (2013)
Arya Mazumdar, Yury Polyanskiy, Barna Saha
On Chebyshev radius of a set in Hamming space and the closest string problem. ISIT (2013)
Xin Luna Dong, Barna Saha, Divesh Srivastava
Less is More: Selecting Sources Wisely for Integration. Proc. VLDB Endow. 6 (2) (2012)
Barna Saha, Samir Khuller
Set Cover Revisited: Hypergraph Cover with Hard Capacities. ICALP (1) (2012)
Samir Khuller, Barna Saha, Kanthi K. Sarpatwar
New Approximation Results for Resource Replication Problems. APPROX-RANDOM (2012)
Lukasz Golab, Howard J. Karloff, Flip Korn, Barna Saha, Divesh Srivastava
Discovering Conservation Rules. ICDE (2012)
Jian Li, Barna Saha, Amol Deshpande
A unified approach to ranking in probabilistic databases. VLDB J. 20 (2) (2011)

Barna Saha.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Barna Saha