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

Journal Publications.

Conference Publications.


  • 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.
    • [The conference proceedings version has an error which has been fixed in the arxiv version. Please refer to arxiv for the corrected version.]
  • Robust Entity Resolution using Random Graphs, Sainyam Galhotra, Donatella Firmani, Barna Saha, Divesh Srivastava, SIGMOD 2018.




  • 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.
    An earlier version appeared on arxiv under a different name.
    Preprint on arxiv.
  • 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.





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


Before 2010


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