Publications.

Author names are in alphabetical order in most of my publications as per tradition in TCS.

Journal Publications. [Outdated–see DBLP instead]

• 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. 48(2): 481-512 (2019)

• A New Approximation Technique for Resource-Allocation Problems, Barna Saha, Aravind Srinivasan, Random Structure & Algorithms, 2018.

• Robust Entity Resolution Using a CrowdOracle, Donatella Firmani, Sainyam Galhotra, Barna Saha, Divesh Srivastava: IEEE Data Eng. Bull. 2018.
• Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, Karl Bringmann, Fabrizio Grandoni, Barna Saha and Virginia Williams. SIAM Journal of Computing, Accepted. (Best Paper Issue of FOCS 2017)
• New Approximation Results for Resource Replication Problems,
  with Samir Khuller and Kanthi Sarpatwar.
  Algorithmica, 2015.
• Facility location with matroid or knapsack constraints ,
  with Ravishankar Krishnaswamy, Amit Kumar, Vishwanath Nagarajan and Yogish Sabharwal.
  Mathematics of Operations Research, 2014.
• Discovering Conservation Rules,
  with Lukasz Golab, Howard Karloff, Flip Korn and Divesh Srivastava.
  IEEE Transactions on Knowledge and Data Engineering (TKDE) 2014. Special Issue on the Best Papers of ICDE 2012.
• A Constant Factor Approximation Algorithm for Fault Tolerant k-Median Problem,
  with Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li and Shi Li.
  Accepted, Transactions on Algorithms, 2015.
• Online Competitive Algorithms for Ad Allocation in Cellular Networks (AdCell),
  with Saeed Alaei, Mohammad Taghi Hajiaghayi, Vahid Liaghat and Dan Pei.
  Under Submission, Transactions on Algorithms, 2012.
• A Unified Approach to Ranking in Probabilistic Databases,
  with Jian Li and Amol Deshpande.
  The VLDB Journal, 2011. Special Issue on the Best Papers from VLDB 2009.
• New Constructive Aspects of the Lovasz Local Lemma,
  with Bernhard Haeupler and Aravind Srinivasan.
  Journal of the ACM (JACM), 2011.

Conference Publications. [Outdated–see DBLP instead]

2021

• 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 Paper, SIGMOD 2021
• Efficient and Effective ER with Progressive Blocking, Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava, VLDB J., 2021

2020:

• 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.

2019

• Sublinear Algorithms for Gap Edit Distance, Elazar Goldenberg, Robert Krauthgamer, Barna Saha, FOCS 2019.
• Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost, Barna Saha, Sanjay Subramanian, ESA 2019, Track B.
• Connectivity in Random Annulus Graphs and the Geometric Block Model, Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha, RANDOM 2019.
• Dynamic Set Cover: Improved Algorithms & Lower Bounds, Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi , Barna Saha, STOC 2019
• Paper Matching with Local Fairness Constraints, Ari Kobren, Barna Saha, Andrew McCallum, KDD 2019. Oral Presentation.
• Min-Max Correlation Clustering via MultiCut, Saba Ahmadi, Samir Khuller, Barna Saha, IPCO 2019.

2018

• The Geometric Block Model, Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha, AAAI 2018.
  • Shorter version in NIPS 2017, Workshop on Learning on Distributions, Functions, Graphs and Groups.

• Robust Entity Resolution using Random Graphs, Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava, SIGMOD 2018.

The Most Reproducible Paper Award

2017

• Fast & Space-Efficient Approximations of Language Edit Distance and RNA-Folding: An Amnesic Dynamic Programming Approach, Barna Saha,
  58th IEEE Symposium on Foundations of Computer Science (FOCS) 2017.
• Query Complexity of Clustering with Side Information, Arya Mazumdar and Barna Saha,The Thirty-first Annual Conference on Neural Information Processing Systems (NIPS) 2017.
• Clustering with Noisy Queries, Arya Mazumdar and Barna Saha, The Thirty-first Annual Conference on Neural Information Processing Systems (NIPS) 2017.
• Approximation Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard! Rajesh Jayaram and Barna Saha. The 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017. Full version
• A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution, Arya Mazumdar, Barna Saha.
  The 31st AAAI Conference on Artificial Intelligence, (AAAI), 2017.

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 and Virginia Williams.
  57th IEEE Symposium on Foundations of Computer Science (FOCS) 2016.
  [Invited to the special issue of best papers of FOCS’16]
• Online Entity Resolution with an Oracle,
  Donatella Firmani, Barna Saha, Divesh Srivastava,
  42nd International Conference on Very Large Data Bases (VLDB) 2016.

2015

• Language Edit Distance & Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms & Connection to Fundamental Graph Problems,
  Barna Saha
  56th IEEE Symposium on Foundations of Computer Science (FOCS) 2015.
  There is an error in the analysis that invalidates the result of arxiv. We were able to correct the error with a somewhat worse bound of n^2.491 as opposed to n^\omega.
• TreeScope: Finding Structural Anomalies In Semi-Structured Data,
  with Shanshan Ying, Flip Korn, and Divesh Srivastava.
  41st International Conference on Very Large Data Bases  (VLDB), 2015.
• Size-constrained Weighted Set Cover,
  with Lukasz Golab, Flip Korn, Feng Li and Divesh Srivastava.
  31st IEEE International Conference on Data Engineering (ICDE) 2015.

2014

• The Dyck Language Edit Distance Problem in Near-linear Time,
  Barna Saha
  55th IEEE Symposium on Foundations of Computer Science (FOCS) 2014.
  An earlier version appeared on arxiv under a different name.
• A Constant Factor Approximation Algorithm for Fault Tolerant k-Median Problem,
  with Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li and Shi Li.
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
• Hierarchical Graph Partitioning,
  with Mohammadtaghi Hajiaghayi, Theodore Johnson and Reza Khani.
  26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2014.
• Data Quality: The other Face of Big Data,
  with Divesh Srivastava.
  Tutorial, 30th IEEE International Conference on Data Engineering (ICDE), 2014.
• Distributed Data Placement to Minimize Communication Costs via Graph Partitioning,
  with Lukasz Golab, Marios Hadjieleftheriou, and Howard Karloff.
  26th International Conference on Scientific and Statistical Database Management (SSDBM), 2014.

2013

• Renting a Cloud,
  Barna Saha
  Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2013.
• Firewall Placement on Cloud Data Centers,
  with Manish Purohit Ahn and Seungjoon Lee.
  Proc. ACM Symposium on Cloud Computing (SOCC), 2013.
• On Repairing Structural Problems in Semi-structured Data,
  with Flip Korn, Divesh Srivastava and Shanshan Ying.
  35th International Conference on Very Large Data Bases (VLDB), 2013.
• Less is More, Selecting Sources Wisely for Integration,
  with Xin Luna Dong and Divesh Srivastava.
  35th International Conference on Very Large Data Bases (VLDB), 2013.
• On Chebyshev Radius of a Set in Hamming Space and the Closest String Problem ,
  with Yury Polyanskiy and Arya Mazumdar.
  IEEE International Symposium on Information Theory (ISIT), 2013.

2012

• New Approximation Results for Resource Replication Problems,
  with Samir Khuller and Kanthi Sarpatwar.
  15th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012.
• Set Cover revisited: Hypergraph Cover with Hard Capacities,
  with Samir Khuller.
  International Colloquium on Automata, Languages, and Programming (ICALP, Track A), 2012.
  This paper settles an open question raised by Chuzhoy and Naor in [FOCS02].
• Discovering Conservation Rules,
  with Lukasz Golab, Howard Karloff, Flip Korn and Divesh Srivastava.
  28th IEEE International Conference on Data Engineering (ICDE), 2012.
  [Invited to IEEE Transactions on Knowledge and Data Engineering (TKDE) special issue on the best papers of ICDE 2012.]

2011

• The Matroid Median Problem,
  with Ravishankar Krishnaswamy and Vishwanath Nagarajan.
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
  Merged with a paper by Amit Kumar and Yogish Sabharwal who obtained similar results for the case of partition matroid.
• AdCell-Ad Allocation in Cellular Networks,
  with Saeed Alaei, Mohammad Taghi Hajiaghayi, Vahid Liaghat and Dan Pei.
  European Symposia on Algorithms (ESA), 2011.
  Here is a much polished version for the online algorithm. Link.
• On Capacitated Set Cover Problems,
  with Nikhil Bansal and Ravishankar Krishnaswamy.
  14th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2011.
• Link Prediction for Annotation Graphs,
  with Philip Anderson, Samir Khuller, Saket Navlakha, Louiqa Raschid, Andreas Thor and Xiao-Ning Zhang.
  International Semantic Web Conference (ISWC), 2011.

2010

• New Constructive Aspects of the Lovasz Local Lemma,
  with Bernhard Haeupler and Aravind Srinivasan.
  IEEE Symposium on Foundations of Computer Science (FOCS) 2010
  This paper settles an outstanding open question related to resource allocation, known as the Santa Claus problem.
• Energy Efficient Scheduling via Partial Shutdown,
  with Samir Khuller and Jian Li.
  ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
• A New Approximation Technique for Resource-Allocation Problems,
  with Aravind Srinivasan.
  Innovations in Theoretical Computer Science (ITCS) 2010, known as ICS at that time.
• Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs,
  with Allison Hoch, Samir Khuller, Louiqa Raschid and Xiao-Ning Zhang.
  International Conference on Research in Computational Molecular Biology (RECOMB) 2010.
• Schema Covering: A Step Towards Enabling Reusability in Information Integration,
  with Ioana Stanoi and Ken Clarkson.
  Proc. 26th IEEE International Conference on Data Engineering (ICDE), 2010.

Before 2010

• A Unified Approach to Ranking in Probabilistic Databases,
  with Jian Li and Amol Deshpande.
  35th International Conference on Very Large Data Bases (VLDB), 2009. BEST PAPER AWARD
• On Finding Dense Subgraphs,
  with Samir Khuller.
  International Colloquium on Automata, Languages, and Programming (ICALP), 2009.
  A longer version is available here.
• On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch,
  with Lise Getoor.
  Ninth SIAM International Conference on Data Mining (SDM), 2009.
• Simplifying Information Integration: Object-Based Flow-of-Mappings Framework for Integration,
  with Bogdan Alexe, Michael Gubanov, Mauricio A. Hernandez, Howard Ho, Jen-Wei Huang,
  Yannis Katsis, Lucian Popa and Ioana Stanoi.
  Lecture Notes in Business Information Processing, Revised Selected Papers from
  Second International VLDB Workshop, BIRTE 2008.
• Group Proximity Measure for Recommending Groups in Online Social Networks.,
  with Lise Getoor.
  2nd ACM SIGKDD Workshop on Social Network Mining and Analysis (SNA-KDD), 2008.
• On Estimating Path-Aggregates over Streaming Graphs,
  with Sumit Ganguly.
  17th International Symposium on Algorithms and Computations (ISAAC), 2006.
• Bidirectional Fuzzy-Regression Model for Road-lines Detection,
  with Arya Mazumdar, N R Pal.
  IEEE International Conference on Engineering of Intelligent Systems (ICEIS), 2006.

Patents

• LukaszGolab, Howard Karloff, Flip Korn, Barna Saha, DiveshSrivastava, “Conservation Dependency,” US patent  US20120130935, AT&T Research Laboratory, New Jersey, 2012.