Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree. - Barna Saha; Pabitra Mitra (ICDM Workshops, 2006)

On Estimating Path Aggregates over Streaming Graphs. - Sumit Ganguly; Barna Saha (ISAAC, 2006)

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 001; Barna Saha; Ioana Stanoi (BIRTE, 2008)

On Finding Dense Subgraphs. - Samir Khuller; Barna Saha (ICALP (1), 2009)

On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch. - Barna Saha; Lise Getoor (SDM, 2009)

A Unified Approach to Ranking in Probabilistic Databases. - Jian Li 015; Barna Saha; Amol Deshpande (Proc. VLDB Endow., 2009)

Schema covering: a step towards enabling reuse in information integration. - Barna Saha; Ioana Stanoi; Kenneth L. Clarkson (ICDE, 2010)

Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. - Barna Saha; Allison Hoch; Samir Khuller; Louiqa Raschid; Xiao-Ning Zhang (RECOMB, 2010)

Energy Efficient Scheduling via Partial Shutdown. - Samir Khuller; Jian Li 015; Barna Saha (SODA, 2010)

On Capacitated Set Cover Problems. - Nikhil Bansal 001; Ravishankar Krishnaswamy; Barna Saha (APPROX-RANDOM, 2011)

AdCell: Ad Allocation in Cellular Networks. - Saeed Alaei; Mohammad Taghi Hajiaghayi; Vahid Liaghat; Dan Pei; Barna Saha (ESA, 2011)

Link Prediction for Annotation Graphs Using Graph Summarization. - Andreas Thor; Philip Anderson 003; Louiqa Raschid; Saket Navlakha; Barna Saha; Samir Khuller; Xiao-Ning Zhang (ISWC (1), 2011)

The Matroid Median Problem. - Ravishankar Krishnaswamy; Amit Kumar 001; Viswanath Nagarajan; Yogish Sabharwal; Barna Saha (SODA, 2011)

New Constructive Aspects of the Lovász Local Lemma. - Bernhard Haeupler; Barna Saha; Aravind Srinivasan (J. ACM, 2011)

Approximation Algorithms for Resource Allocation. - Barna Saha (2011)

Set Cover Revisited: Hypergraph Cover with Hard Capacities. - Barna Saha; Samir Khuller (ICALP (1), 2012)

Less is More: Selecting Sources Wisely for Integration. - Xin Luna Dong; Barna Saha; Divesh Srivastava (Proc. VLDB Endow., 2012)

Firewall placement in cloud data centers. - Seungjoon Lee; Manish Purohit; Barna Saha (SoCC, 2013)

Renting a Cloud. - Barna Saha (FSTTCS, 2013)

On Chebyshev radius of a set in Hamming space and the closest string problem. - Arya Mazumdar; Yury Polyanskiy; Barna Saha (ISIT, 2013)

Distributed Data Placement via Graph Partitioning. - Lukasz Golab; Marios Hadjieleftheriou; Howard J. Karloff; Barna Saha (CoRR, 2013)

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median. - Mohammad Taghi Hajiaghayi; Wei Hu; Jian Li 015; Shi Li 001; Barna Saha (CoRR, 2013)

Efficiently Computing Edit Distance to Dyck Language. - Barna Saha (CoRR, 2013)

On Repairing Structural Problems In Semi-structured Data. - Flip Korn; Barna Saha; Divesh Srivastava; Shanshan Ying (Proc. VLDB Endow., 2013)

The Dyck Language Edit Distance Problem in Near-Linear Time. - Barna Saha (FOCS, 2014)

Data quality: The other face of Big Data. - Barna Saha; Divesh Srivastava (ICDE, 2014)

Hierarchical graph partitioning. - Mohammad Taghi Hajiaghayi; Theodore Johnson; Mohammad Reza Khani; Barna Saha (SPAA, 2014)

Distributed data placement to minimize communication costs via graph partitioning. - Lukasz Golab; Marios Hadjieleftheriou; Howard J. Karloff; Barna Saha (SSDBM, 2014)

Faster Language Edit Distance, Connection to All-pairs Shortest Paths and Related Problems. - Barna Saha (CoRR, 2014)

Discovering Conservation Rules. - Lukasz Golab; Howard J. Karloff; Flip Korn; Barna Saha; Divesh Srivastava (IEEE Trans. Knowl. Data Eng., 2014)

Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. - Barna Saha (FOCS, 2015)

Size-Constrained Weighted Set Cover. - Lukasz Golab; Flip Korn; Feng Li; Barna Saha; Divesh Srivastava (ICDE, 2015)

Facility Location with Matroid or Knapsack Constraints. - Ravishankar Krishnaswamy; Amit Kumar 001; Viswanath Nagarajan; Yogish Sabharwal; Barna Saha (Math. Oper. Res., 2015)

TreeScope: Finding Structural Anomalies In Semi-Structured Data. - Shanshan Ying; Flip Korn; Barna Saha; Divesh Srivastava (Proc. VLDB Endow., 2015)

Clustering with an oracle. - Arya Mazumdar; Barna Saha (Allerton, 2016)

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. - Karl Bringmann; Fabrizio Grandoni 001; Barna Saha; Virginia Vassilevska Williams (FOCS, 2016)

New Approximation Results for Resource Replication Problems. - Samir Khuller; Barna Saha; Kanthi K. Sarpatwar (Algorithmica, 2016)

Clustering Via Crowdsourcing. - Arya Mazumdar; Barna Saha (CoRR, 2016)

Online Entity Resolution Using an Oracle. - Donatella Firmani; Barna Saha; Divesh Srivastava (Proc. VLDB Endow., 2016)

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median. - Mohammad Taghi Hajiaghayi; Wei Hu; Jian Li 015; Shi Li 001; Barna Saha (ACM Trans. Algorithms, 2016)

A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution. - Arya Mazumdar; Barna Saha (AAAI, 2017)

Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. - Barna Saha (FOCS, 2017)

Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!. - Rajesh Jayaram; Barna Saha (ICALP, 2017)

Query Complexity of Clustering with Side Information. - Arya Mazumdar; Barna Saha (NIPS, 2017)

Clustering with Noisy Queries. - Arya Mazumdar; Barna Saha (NIPS, 2017)

The Geometric Block Model. - Sainyam Galhotra; Arya Mazumdar; Soumyabrata Pal; Barna Saha (AAAI, 2018)

The Geometric Block Model and Applications. - Sainyam Galhotra; Soumyabrata Pal; Arya Mazumdar; Barna Saha (Allerton, 2018)

Robust Entity Resolution using Random Graphs. - Sainyam Galhotra; Donatella Firmani; Barna Saha; Divesh Srivastava (SIGMOD Conference, 2018)

Fully Dynamic Set Cover - Improved and Simple. - Raghavendra Addanki; Barna Saha (CoRR, 2018)

Robust Entity Resolution Using a CrowdOracle. - Donatella Firmani; Sainyam Galhotra; Barna Saha; Divesh Srivastava (IEEE Data Eng. Bull., 2018)

A new approximation technique for resource-allocation problems. - Barna Saha; Aravind Srinivasan (Random Struct. Algorithms, 2018)

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue. - Arnab Bhattacharyya 001; Fabrizio Grandoni 001; Aleksandar Nikolov; Barna Saha; Saket Saurabh 001; Aravindan Vijayaraghavan; Qin Zhang 001 (ACM Trans. Algorithms, 2018)

Connectivity of Random Annulus Graphs and the Geometric Block Model. - Sainyam Galhotra; Arya Mazumdar; Soumyabrata Pal; Barna Saha (APPROX-RANDOM, 2019)

Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. - Barna Saha; Sanjay Subramanian (ESA, 2019)

Sublinear Algorithms for Gap Edit Distance. - Elazar Goldenberg; Robert Krauthgamer; Barna Saha (FOCS, 2019)

Min-Max Correlation Clustering via MultiCut. - Saba Ahmadi; Samir Khuller; Barna Saha (IPCO, 2019)

Paper Matching with Local Fairness Constraints. - Ari Kobren; Barna Saha; Andrew McCallum (KDD, 2019)

Crowd-Sourced Entity Resolution with Control Queries. - Sainyam Galhotra; Donatella Firmani; Barna Saha; Divesh Srivastava (SEBD, 2019)

Dynamic set cover: improved algorithms and lower bounds. - Amir Abboud; Raghavendra Addanki; Fabrizio Grandoni 001; Debmalya Panigrahi; Barna Saha (STOC, 2019)

Min-Max Correlation Clustering via MultiCut. - Saba Ahmadi; Sainyam Galhotra; Samir Khuller; Barna Saha; Roy Schwartz 002 (CoRR, 2019)

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product. - Karl Bringmann; Fabrizio Grandoni 001; Barna Saha; Virginia Vassilevska Williams (SIAM J. Comput., 2019)

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. - Tomasz Kociumaka; Barna Saha (FOCS, 2020)

Does preprocessing help in fast sequence comparisons? - Elazar Goldenberg; Aviad Rubinstein; Barna Saha (STOC, 2020)

Fair Correlation Clustering. - Saba Ahmadi; Sainyam Galhotra; Barna Saha; Roy Schwartz 002 (CoRR, 2020)

Sublinear Algorithms for Edit Distance (Invited Talk). - Barna Saha (MFCS, 2021)

Approximation Algorithms for Large Scale Data Analysis. - Barna Saha (PODS, 2021)

BEER: Blocking for Effective Entity Resolution. - Sainyam Galhotra; Donatella Firmani; Barna Saha; Divesh Srivastava (SIGMOD Conference, 2021)

The Complexity of Average-Case Dynamic Subgraph Counting. - Monika Henzinger; Andrea Lincoln; Barna Saha (Electron. Colloquium Comput. Complex., 2021)

How to Design Robust Algorithms using Noisy Comparison Oracle. - Raghavendra Addanki; Sainyam Galhotra; Barna Saha (Proc. VLDB Endow., 2021)

Efficient and effective ER with progressive blocking. - Sainyam Galhotra; Donatella Firmani; Barna Saha; Divesh Srivastava (VLDB J., 2021)

Approximating LCS and Alignment Distance over Multiple Sequences. - Debarati Das 001; Barna Saha (APPROX/RANDOM, 2022)

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. - Debarati Das 001; Jacob Gilbert; MohammadTaghi Hajiaghayi; Tomasz Kociumaka; Barna Saha; Hamed Saleh (FOCS, 2022)

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. - Elazar Goldenberg; Tomasz Kociumaka; Robert Krauthgamer; Barna Saha (FOCS, 2022)

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. - Debarati Das 001; Tomasz Kociumaka; Barna Saha (ICALP, 2022)

Hierarchical Entity Resolution using an Oracle. - Sainyam Galhotra; Donatella Firmani; Barna Saha; Divesh Srivastava (SIGMOD Conference, 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)

Approximating Edit Distance in the Fully Dynamic Model. - Tomasz Kociumaka; Anish Mukherjee 001; Barna Saha (FOCS, 2023)

An Algorithmic Bridge Between Hamming and Levenshtein Distances. - Elazar Goldenberg; Tomasz Kociumaka; Robert Krauthgamer; Barna Saha (ITCS, 2023)

Weighted Edit Distance Computation: Strings, Trees, and Dyck. - Debarati Das 001; Jacob Gilbert; MohammadTaghi Hajiaghayi; Tomasz Kociumaka; Barna Saha (STOC, 2023)

On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. - Monika Henzinger; Andrea Lincoln; Barna Saha; Martin P. Seybold; Christopher Ye 001 (CoRR, 2023)

Community Recovery in the Geometric Block Model. - Sainyam Galhotra; Arya Mazumdar; Soumyabrata Pal; Barna Saha (J. Mach. Learn. Res., 2023)

I/O Complexity of Attention, or How Optimal is FlashAttention? - Barna Saha; Christopher Ye 001 (ICML, 2024)

On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. - Monika Henzinger; Barna Saha; Martin P. Seybold; Christopher Ye 001 (ITCS, 2024)

Role of Structured Matrices in Fine-Grained Algorithm Design (Invited Talk). - Barna Saha (ISAAC, 2024)

Clustering with Non-adaptive Subset Queries. - Hadley Black; Euiwoong Lee; Arya Mazumdar; Barna Saha (NeurIPS, 2024)

Building Taxonomies with Triplet Queries. - Donatella Firmani; Sainyam Galhotra; Barna Saha; Divesh Srivastava (SEBD, 2024)

Faster Approximate All Pairs Shortest Paths. - Barna Saha; Christopher Ye 001 (SODA, 2024)

Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC. - Debarati Das 001; Jacob Gilbert; MohammadTaghi Hajiaghayi; Tomasz Kociumaka; Barna Saha (SPAA, 2024)

The I/O Complexity of Attention, or How Optimal is Flash Attention? - Barna Saha; Christopher Ye 001 (CoRR, 2024)

Learning Partitions with Optimal Query and Round Complexities. - Hadley Black; Arya Mazumdar; Barna Saha (COLT, 2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs. - Hadley Black; Arya Mazumdar; Barna Saha; Yinzhan Xu (COLT, 2025)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More. - Mina Dalirrooyfard; Andrea Lincoln; Barna Saha; Virginia Vassilevska Williams (SODA, 2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More. - Barna Saha; Virginia Vassilevska Williams; Yinzhan Xu; Christopher Ye 001 (SODA, 2025)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence. - Jakob Nogler; Adam Polak 001; Barna Saha; Virginia Vassilevska Williams; Yinzhan Xu; Christopher Ye 001 (STOC, 2025)

Subquadratic Algorithms and Hardness for Attention with Any Temperature. - Shreya Gupta; Boyang Huang; Barna Saha; Yinzhan Xu; Christopher Ye 001 (CoRR, 2025)