Publications

Publications.

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

Journal Publications.

  1. New Approximation Results for Resource Replication Problems,
    with Samir Khuller and Kanthi Sarpatwar.
    Algorithmica, 2015.
  2. Facility location with matroid or knapsack constraints ,
    with Ravishankar Krishnaswamy, Amit Kumar, Vishwanath Nagarajan and Yogish Sabharwal.
    Mathematics of Operations Research, 2014.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. New Constructive Aspects of the Lovasz Local Lemma,
    with Bernhard Haeupler and Aravind Srinivasan.
    Journal of the ACM (JACM), 2011.

Conference Publications.

  1. 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
  2. A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution, Arya Mazumdar, Barna Saha.
    The 31st AAAI Conference on Artificial Intelligence, (AAAI), 2017.
  3. 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]
  4. Online Entity Resolution with an Oracle,
    Donatella Firmani, Barna Saha, Divesh Srivastava,
    42nd International Conference on Very Large Data Bases (VLDB) 2016.
  5. 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.
  6. 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, (Demo).
  7. Size-constrained Weighted Set Cover,
    with Lukasz Golab, Flip Korn, Feng Li and Divesh Srivastava.
    31st IEEE International Conference on Data Engineering (ICDE) 2015.
  8. 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.
  9. 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.
  10. Hierarchical Graph Partitioning,
    with Mohammadtaghi Hajiaghayi, Theodore Johnson and Reza Khani.
    26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2014.
  11. Data Quality: The other Face of Big Data,
    with Divesh Srivastava.
    Tutorial, 30th IEEE International Conference on Data Engineering (ICDE), 2014.
  12. 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.
  13. Renting a Cloud,
    Barna Saha
    Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2013.
  14. Firewall Placement on Cloud Data Centers,
    with Manish Purohit Ahn and Seungjoon Lee.
    Poster, Proc. ACM Symposium on Cloud Computing (SOCC), 2013.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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].
  20. 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.]
  21. 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.
  22. 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.
  23. On Capacitated Set Cover Problems,
    with Nikhil Bansal and Ravishankar Krishnaswamy.
    14th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2011.
  24. 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.
  25. 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.
  26. Energy Efficient Scheduling via Partial Shutdown,
    with Samir Khuller and Jian Li.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
  27. A New Approximation Technique for Resource-Allocation Problems,
    with Aravind Srinivasan.
    Innovations in Theoretical Computer Science (ITCS) 2010, known as ICS at that time.
  28. 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.
  29. 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.
  30. 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
  31. On Finding Dense Subgraphs,
    with Samir Khuller.
    International Colloquium on Automata, Languages, and Programming (ICALP), 2009.
    A longer version is available here.
  32. 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.
  33. 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.
  34. 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.
  35. On Estimating Path-Aggregates over Streaming Graphs,
    with Sumit Ganguly.
    17th International Symposium on Algorithms and Computations (ISAAC), 2006.
  36. 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 filed US20120130935, AT&T Research Laboratory, New Jersey, 2012.