Barna Saha

According to our database, Barna Saha authored at least 93 papers between 2006 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More.

Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More.

Mina Dalirrooyfard, Andrea Lincoln, Barna Saha, Virginia Vassilevska Williams

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence.

Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye

CoRR, 2024

Clustering with Non-adaptive Subset Queries.

Hadley Black, Euiwoong Lee, Arya Mazumdar, Barna Saha

CoRR, 2024

The I/O Complexity of Attention, or How Optimal is Flash Attention?

Barna Saha, Christopher Ye

CoRR, 2024

Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC.

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha

Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, 2024

Faster Approximate All Pairs Shortest Paths.

Barna Saha, Christopher Ye

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Building Taxonomies with Triplet Queries.

Donatella Firmani, Sainyam Galhotra, Barna Saha, Divesh Srivastava

Proceedings of the 32nd Symposium of Advanced Database Systems, 2024

Role of Structured Matrices in Fine-Grained Algorithm Design (Invited Talk).

Barna Saha

Proceedings of the 35th International Symposium on Algorithms and Computation, 2024

On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.

Monika Henzinger, Barna Saha, Martin P. Seybold, Christopher Ye

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

I/O Complexity of Attention, or How Optimal is FlashAttention?

Barna Saha, Christopher Ye

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

Community Recovery in the Geometric Block Model.

Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha

J. Mach. Learn. Res., 2023

On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.

Monika Henzinger, Andrea Lincoln, Barna Saha, Martin P. Seybold, Christopher Ye

CoRR, 2023

Weighted Edit Distance Computation: Strings, Trees, and Dyck.

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

An Algorithmic Bridge Between Hamming and Levenshtein Distances.

Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Approximating Edit Distance in the Fully Dynamic Model.

Tomasz Kociumaka, Anish Mukherjee, Barna Saha

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

An Upper Bound and Linear-Space Queries on the LZ-End Parsing.

Dominik Kempa, Barna Saha

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

How Compression and Approximation Affect Efficiency in String Distance Measures.

Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Hierarchical Entity Resolution using an Oracle.

Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava

Proceedings of the SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding.

Debarati Das, Tomasz Kociumaka, Barna Saha

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.

Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Approximating LCS and Alignment Distance over Multiple Sequences.

Debarati Das, Barna Saha

Proceedings of the Approximation, 2022

2021

Efficient and effective ER with progressive blocking.

Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava

VLDB J., 2021

How to Design Robust Algorithms using Noisy Comparison Oracle.

Raghavendra Addanki, Sainyam Galhotra, Barna Saha

Proc. VLDB Endow., 2021

The Complexity of Average-Case Dynamic Subgraph Counting.

Monika Henzinger, Andrea Lincoln, Barna Saha

Electron. Colloquium Comput. Complex., 2021

BEER: Blocking for Effective Entity Resolution.

Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava

Proceedings of the SIGMOD '21: International Conference on Management of Data, 2021

Approximation Algorithms for Large Scale Data Analysis.

Barna Saha

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

Sublinear Algorithms for Edit Distance (Invited Talk).

Barna Saha

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020

Fair Correlation Clustering.

Saba Ahmadi, Sainyam Galhotra, Barna Saha, Roy Schwartz

CoRR, 2020

Does preprocessing help in fast sequence comparisons?

Elazar Goldenberg, Aviad Rubinstein, Barna Saha

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.

Tomasz Kociumaka, Barna Saha

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.

Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams

SIAM J. Comput., 2019

Min-Max Correlation Clustering via MultiCut.

Saba Ahmadi, Sainyam Galhotra, Samir Khuller, Barna Saha, Roy Schwartz

CoRR, 2019

Dynamic set cover: improved algorithms and lower bounds.

Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Crowd-Sourced Entity Resolution with Control Queries.

Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava

Proceedings of the 27th Italian Symposium on Advanced Database Systems, 2019

Paper Matching with Local Fairness Constraints.

Ari Kobren, Barna Saha, Andrew McCallum

Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019

Min-Max Correlation Clustering via MultiCut.

Saba Ahmadi, Samir Khuller, Barna Saha

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

Sublinear Algorithms for Gap Edit Distance.

Elazar Goldenberg, Robert Krauthgamer, Barna Saha

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost.

Barna Saha, Sanjay Subramanian

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Connectivity of Random Annulus Graphs and the Geometric Block Model.

Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha

Proceedings of the Approximation, 2019

2018

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue.

Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang

ACM Trans. Algorithms, 2018

A new approximation technique for resource-allocation problems.

Barna Saha, Aravind Srinivasan

Random Struct. Algorithms, 2018

Robust Entity Resolution Using a CrowdOracle.

Donatella Firmani, Sainyam Galhotra, Barna Saha, Divesh Srivastava

IEEE Data Eng. Bull., 2018

Fully Dynamic Set Cover - Improved and Simple.

Raghavendra Addanki, Barna Saha

CoRR, 2018

Robust Entity Resolution using Random Graphs.

Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava

Proceedings of the 2018 International Conference on Management of Data, 2018

The Geometric Block Model and Applications.

Sainyam Galhotra, Soumyabrata Pal, Arya Mazumdar, Barna Saha

Proceedings of the 56th Annual Allerton Conference on Communication, 2018

The Geometric Block Model.

Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

Clustering with Noisy Queries.

Arya Mazumdar, Barna Saha

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Query Complexity of Clustering with Side Information.

Arya Mazumdar, Barna Saha

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!.

Rajesh Jayaram, Barna Saha

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach.

Barna Saha

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution.

Arya Mazumdar, Barna Saha

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

A Constant Factor Approximation Algorithm for Fault-Tolerant <i>k</i>-Median.

Mohammad Taghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha

ACM Trans. Algorithms, 2016

Online Entity Resolution Using an Oracle.

Donatella Firmani, Barna Saha, Divesh Srivastava

Proc. VLDB Endow., 2016

Clustering Via Crowdsourcing.

Arya Mazumdar, Barna Saha

CoRR, 2016

New Approximation Results for Resource Replication Problems.

Samir Khuller, Barna Saha, Kanthi K. Sarpatwar

Algorithmica, 2016

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.

Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Clustering with an oracle.

Arya Mazumdar, Barna Saha

Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015

TreeScope: Finding Structural Anomalies In Semi-Structured Data.

Shanshan Ying, Flip Korn, Barna Saha, Divesh Srivastava

Proc. VLDB Endow., 2015

Facility Location with Matroid or Knapsack Constraints.

Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha

Math. Oper. Res., 2015

Size-Constrained Weighted Set Cover.

Lukasz Golab, Flip Korn, Feng Li, Barna Saha, Divesh Srivastava

Proceedings of the 31st IEEE International Conference on Data Engineering, 2015

Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems.

Barna Saha

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Discovering Conservation Rules.

Lukasz Golab, Howard J. Karloff, Flip Korn, Barna Saha, Divesh Srivastava

IEEE Trans. Knowl. Data Eng., 2014

Faster Language Edit Distance, Connection to All-pairs Shortest Paths and Related Problems.

Barna Saha

CoRR, 2014

Distributed data placement to minimize communication costs via graph partitioning.

Lukasz Golab, Marios Hadjieleftheriou, Howard J. Karloff, Barna Saha

Proceedings of the Conference on Scientific and Statistical Database Management, 2014

Hierarchical graph partitioning.

Mohammad Taghi Hajiaghayi, Theodore Johnson, Mohammad Reza Khani, Barna Saha

Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Data quality: The other face of Big Data.

Barna Saha, Divesh Srivastava

Proceedings of the IEEE 30th International Conference on Data Engineering, Chicago, 2014

The Dyck Language Edit Distance Problem in Near-Linear Time.

Barna Saha

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

On Repairing Structural Problems In Semi-structured Data.

Flip Korn, Barna Saha, Divesh Srivastava, Shanshan Ying

Proc. VLDB Endow., 2013

Efficiently Computing Edit Distance to Dyck Language.

Barna Saha

CoRR, 2013

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median.

Mohammad Taghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha

CoRR, 2013

Distributed Data Placement via Graph Partitioning.

Lukasz Golab, Marios Hadjieleftheriou, Howard J. Karloff, Barna Saha

CoRR, 2013

On Chebyshev radius of a set in Hamming space and the closest string problem.

Arya Mazumdar, Yury Polyanskiy, Barna Saha

Proceedings of the 2013 IEEE International Symposium on Information Theory, 2013

Renting a Cloud.

Barna Saha

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Firewall placement in cloud data centers.

Seungjoon Lee, Manish Purohit, Barna Saha

Proceedings of the ACM Symposium on Cloud Computing, SOCC '13, 2013

2012

Less is More: Selecting Sources Wisely for Integration.

Xin Luna Dong, Barna Saha, Divesh Srivastava

Proc. VLDB Endow., 2012

Set Cover Revisited: Hypergraph Cover with Hard Capacities.

Barna Saha, Samir Khuller

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Approximation Algorithms for Resource Allocation.

Barna Saha

PhD thesis, 2011

New Constructive Aspects of the Lovász Local Lemma.

Bernhard Haeupler, Barna Saha, Aravind Srinivasan

J. ACM, 2011

The Matroid Median Problem.

Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Link Prediction for Annotation Graphs Using Graph Summarization.

Andreas Thor, Philip Anderson, Louiqa Raschid, Saket Navlakha, Barna Saha, Samir Khuller, Xiao-Ning Zhang

Proceedings of the Semantic Web - ISWC 2011, 2011

AdCell: Ad Allocation in Cellular Networks.

Saeed Alaei, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Dan Pei, Barna Saha

Proceedings of the Algorithms - ESA 2011, 2011

On Capacitated Set Cover Problems.

Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Energy Efficient Scheduling via Partial Shutdown.

Samir Khuller, Jian Li, Barna Saha

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs.

Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, Xiao-Ning Zhang

Proceedings of the Research in Computational Molecular Biology, 2010

Schema covering: a step towards enabling reuse in information integration.

Barna Saha, Ioana Stanoi, Kenneth L. Clarkson

Proceedings of the 26th International Conference on Data Engineering, 2010

2009

A Unified Approach to Ranking in Probabilistic Databases.

Jian Li, Barna Saha, Amol Deshpande

Proc. VLDB Endow., 2009

On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch.

Barna Saha, Lise Getoor

Proceedings of the SIAM International Conference on Data Mining, 2009

On Finding Dense Subgraphs.

Samir Khuller, Barna Saha

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Simplifying Information Integration: Object-Based Flow-of-Mappings Framework for Integration.

Bogdan Alexe, Michael N. Gubanov, Mauricio A. Hernández, C. T. Howard Ho, Jen-Wei Huang, Yannis Katsis, Lucian Popa, Barna Saha, Ioana Stanoi

Proceedings of the Business Intelligence for the Real-Time Enterprise, 2008

2006

On Estimating Path Aggregates over Streaming Graphs.

Sumit Ganguly, Barna Saha

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree.

Barna Saha, Pabitra Mitra

Proceedings of the Workshops Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 2006), 2006