| 2026 | COLT | Actively Learning Halfspaces without Synthetic Data. | Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So |
| 2026 | ICALP | Deterministic Monotone Min-Plus Product and Convolution. | Ce Jin, Jaewoo Park, Barna Saha, Yinzhan Xu |
| 2026 | SIGMOD | SynthAI@SIGMOD 2026: Workshop on Synthetic Data Generation and Management for Building AI Systems. | Ramasuri Narayanam, Prasad Deshpande, Srikanta Bedathur, Eugene Wu, Soumyabrata Pal, Subrata Mitra, Eunyee Koh, Barna Saha |
| 2026 | STOC | On the Computational Hardness of Transformers. | Barna Saha, Yinzhan Xu, Christopher Ye, Hantao Yu |
| 2025 | COLT | Learning Partitions with Optimal Query and Round Complexities. | Hadley Black, Arya Mazumdar, Barna Saha |
| 2025 | COLT | Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs. | Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu |
| 2025 | FOCS | Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2025 | SODA | Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More. | Mina Dalirrooyfard, Andrea Lincoln, Barna Saha, Virginia Vassilevska Williams |
| 2025 | SODA | Fine-Grained Optimality of Partially Dynamic Shortest Paths and More. | Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye |
| 2025 | STOC | Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence. | Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye |
| 2024 | ICML | I/O Complexity of Attention, or How Optimal is FlashAttention? | Barna Saha, Christopher Ye |
| 2024 | ISAAC | Role of Structured Matrices in Fine-Grained Algorithm Design (Invited Talk). | Barna Saha |
| 2024 | SODA | Faster Approximate All Pairs Shortest Paths. | Barna Saha, Christopher Ye |
| 2024 | SPAA | Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2023 | FOCS | Approximating Edit Distance in the Fully Dynamic Model. | Tomasz Kociumaka, Anish Mukherjee, Barna Saha |
| 2023 | STOC | Weighted Edit Distance Computation: Strings, Trees, and Dyck. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2022 | FOCS | (n+poly(k))-time Algorithm for Bounded Tree Edit Distance. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh |
| 2022 | FOCS | Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. | Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
| 2022 | ICALP | Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. | Debarati Das, Tomasz Kociumaka, Barna Saha |
| 2022 | SIGMOD | Hierarchical Entity Resolution using an Oracle. | Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava |
| 2022 | SODA | How Compression and Approximation Affect Efficiency in String Distance Measures. | Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha |
| 2022 | SODA | The Complexity of Average-Case Dynamic Subgraph Counting. | Monika Henzinger, Andrea Lincoln, Barna Saha |
| 2022 | SODA | An Upper Bound and Linear-Space Queries on the LZ-End Parsing. | Dominik Kempa, Barna Saha |
| 2021 | MFCS | Sublinear Algorithms for Edit Distance (Invited Talk). | Barna Saha |
| 2021 | PODS | Approximation Algorithms for Large Scale Data Analysis. | Barna Saha |
| 2021 | SIGMOD | BEER: Blocking for Effective Entity Resolution. | Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava |
| 2020 | FOCS | Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. | Tomasz Kociumaka, Barna Saha |
| 2020 | STOC | Does preprocessing help in fast sequence comparisons? | Elazar Goldenberg, Aviad Rubinstein, Barna Saha |
| 2019 | ESA | Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. | Barna Saha, Sanjay Subramanian |
| 2019 | FOCS | Sublinear Algorithms for Gap Edit Distance. | Elazar Goldenberg, Robert Krauthgamer, Barna Saha |
| 2019 | IPCO | Min-Max Correlation Clustering via MultiCut. | Saba Ahmadi, Samir Khuller, Barna Saha |
| 2019 | KDD | Paper Matching with Local Fairness Constraints. | Ari Kobren, Barna Saha, Andrew McCallum |
| 2019 | STOC | Dynamic set cover: improved algorithms and lower bounds. | Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha |
| 2018 | AAAI | The Geometric Block Model. | Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha |
| 2018 | SIGMOD | Robust Entity Resolution using Random Graphs. | Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava |
| 2017 | AAAI | A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution. | Arya Mazumdar, Barna Saha |
| 2017 | FOCS | Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. | Barna Saha |
| 2017 | ICALP | Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!. | Rajesh Jayaram, Barna Saha |
| 2016 | FOCS | 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 |
| 2015 | FOCS | Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. | Barna Saha |
| 2015 | ICDE | Size-Constrained Weighted Set Cover. | Lukasz Golab, Flip Korn, Feng Li, Barna Saha, Divesh Srivastava |
| 2014 | FOCS | The Dyck Language Edit Distance Problem in Near-Linear Time. | Barna Saha |
| 2014 | ICDE | Data quality: The other face of Big Data. | Barna Saha, Divesh Srivastava |
| 2014 | SODA | A Constant Factor Approximation Algorithm for Fault-Tolerant | MohammadTaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha |
| 2014 | SPAA | Hierarchical graph partitioning. | Mohammad Taghi Hajiaghayi, Theodore Johnson, Mohammad Reza Khani, Barna Saha |
| 2014 | SSDBM | Distributed data placement to minimize communication costs via graph partitioning. | Lukasz Golab, Marios Hadjieleftheriou, Howard J. Karloff, Barna Saha |
| 2013 | CLOUD | Firewall placement in cloud data centers. | Seungjoon Lee, Manish Purohit, Barna Saha |
| 2013 | ISIT | On Chebyshev radius of a set in Hamming space and the closest string problem. | Arya Mazumdar, Yury Polyanskiy, Barna Saha |
| 2012 | ICALP | Set Cover Revisited: Hypergraph Cover with Hard Capacities. | Barna Saha, Samir Khuller |
| 2012 | ICDE | Discovering Conservation Rules. | Lukasz Golab, Howard J. Karloff, Flip Korn, Barna Saha, Divesh Srivastava |
| 2011 | ESA | AdCell: Ad Allocation in Cellular Networks. | Saeed Alaei, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Dan Pei, Barna Saha |
| 2011 | SODA | The Matroid Median Problem. | Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha |
| 2010 | FOCS | New Constructive Aspects of the Lovasz Local Lemma. | Bernhard Haeupler, Barna Saha, Aravind Srinivasan |
| 2010 | ICDE | Schema covering: a step towards enabling reuse in information integration. | Barna Saha, Ioana Stanoi, Kenneth L. Clarkson |
| 2010 | RECOMB | Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. | Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, Xiao-Ning Zhang |
| 2010 | SODA | Energy Efficient Scheduling via Partial Shutdown. | Samir Khuller, Jian Li, Barna Saha |
| 2009 | ICALP | On Finding Dense Subgraphs. | Samir Khuller, Barna Saha |
| 2009 | SDM | On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch. | Barna Saha, Lise Getoor |
| 2007 | SDM | Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree. | Barna Saha, Pabitra Mitra |
| 2006 | ICDM | Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree. | Barna Saha, Pabitra Mitra |
| 2006 | ISAAC | On Estimating Path Aggregates over Streaming Graphs. | Sumit Ganguly, Barna Saha |