Barna Saha

Back to Homepage

PUBLICATIONS

    Publications by Choronological Order:


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

    My DBLP list of publications

    Journal Publications

  1. “Discovering Conservation Rules”,
        with Lukasz Golab, Howard Karloff, Flip Korn and Divesh Srivastava.
        To appear in IEEE Transactions on Knowledge and Data Engineering (TKDE) Special Issue on the Best Papers of ICDE 2012.

  2. “A Unified Approach to Ranking in Probabilistic Databases”,
        with Jian Li and Amol Deshpande.
        The VLDB Journal Special Issue on the Best Papers from VLDB 2009, 20(2), 245-279.

  3. “ New Constructive Aspects of the Lovasz Local Lemma” ,
        with Bernhard Haeupler and Aravind Srinivasan.
        Journal of the ACM (JACM), 58(6), 28.

    Under Submission

  4. “Fault Tolerant Facility Location and k-Median Problem”,
        with Mohammadtaghi Hajiaghayi and Jian Li.
        Submitted.

  5. “Summarizing Event Response Data”,
        with Lukasz Golab, Flip Korn, Feng Li and Divesh Srivastava.
        Submitted.

  6. “Repairing Malformed Semi-structured Data”,
        with Flip Korn, Divesh Srivastava and Shanshan Yang.
        Submitted.

  7. “Renting a Cloud”,
        with Howard Karloff.
        Submitted.

  8. “ Error Model in Record Linkage via Correlation Clustering”,
        with Donatella Firmani and Divesh Srivastava.
        In Preparation.

    Conference Publications

  9. “Less is More, Selecting Sources Wisely for Integration”,
        with Xin Luna Dong and Divesh Srivastava.
        Accepted 35th International Conference on Very Large Data Bases (VLDB), 2013 .

  10. “The Closest String Problem and the Chebyshev Radius”,
        with Yury Polyanskiy and Arya Mazumdar.
        Accepted IEEE International Symposium on Information Theory (ISIT), 2013 .
    We give a surprisingly simple solution to the closest string problem improving upon a long series of previous works.

  11. “New Approximation Results for Resource Replication Problems”,
        with Samir Khuller and Kanthi Sarpatwar.
        Proc. 15th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012

  12. “Set Cover revisited: Hypergraph Cover with Hard Capacities”,
        with Samir Khuller.
        Proc. International Colloquium on Automata, Languages, and Programming (ICALP, Track A), 2012.
    This paper settles an open question raised by Chuzhoy and Naor in [FOCS06].

  13. “Discovering Conservation Rules”,
        with Lukasz Golab, Howard Karloff, Flip Korn and Divesh Srivastava.
        Proc. 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.

  14. “The Matroid Median Problem”,
        with Ravishankar Krishnaswamy and Vishwanath Nagarajan.
        Proc. 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.

  15. “AdCell-Ad Allocation in Cellular Networks”,
        with Saeed Alaei, Mohammad Taghi Hajiaghayi, Vahid Liaghat and Dan Pei.
        Proc. European Symposia on Algorithms (ESA), 2011

  16. “On Capacitated Set Cover Problems”,
        with Nikhil Bansal and Ravishankar Krishnaswamy.
        Proc. 14th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2011

  17. “Link Prediction for Annotation Graphs”,
        with Philip Anderson, Samir Khuller, Saket Navlakha, Louiqa Raschid, Andreas Thor and Xiao-Ning Zhang.
        Proc. International Semantic Web Conference (ISWC), 2011

  18. “ New Constructive Aspects of the Lovasz Local Lemma” ,
        with Bernhard Haeupler and Aravind Srinivasan.
        Proc. IEEE Symposium on Foundations of Computer Science (FOCS) 2010
        Arxiv full-version: “ CoRR Technical Report arXiv:1001.1231”
    This paper settles an outstanding open question related to resource allocation, known as the Santa Claus problem.

  19. “Energy Efficient Scheduling via Partial Shutdown”,
        with Samir Khuller and Jian Li.
        Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010 .

  20. “A New Approximation Technique for Resource-Allocation Problems”,
        with Aravind Srinivasan.
        Proc. Innovations in Theoretical Computer Science (ITCS) 2010 , [Talk Slides] .

  21. “Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs”,
        with Allison Hoch, Samir Khuller, Louiqa Raschid and Xiao-Ning Zhang.
        Proc. International Conference on Research in Computational Molecular Biology (RECOMB) 2010

  22. “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 .

  23. “A Unified Approach to Ranking in Probabilistic Databases”,
        with Jian Li and Amol Deshpande.
        Proc. 35th International Conference on Very Large Data Bases (VLDB), 2009 (BEST PAPER AWARD)
        “ CoRR Technical Report arXiv:0904.1366”, [Talk Slides]

  24. “On Finding Dense Subgraphs”,
        with Samir Khuller.
        Proc. International Colloquium on Automata, Languages, and Programming (ICALP, Track A), 2009 , [Talk Slides] .

  25. “On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch”,
        with Lise Getoor.
        Proc. Ninth SIAM International Conference on Data Mining (SDM), 2009.

  26. “ Simplifying Information Integration: Object-Based Flow-of-Mappings Framework for Integration”,
        with Bogdan Alexe, Michael Gubanov, Mauricio A. Hernαndez, 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
    .

  27. “Group Proximity Measure for Recommending Groups in Online Social Networks.",
        with Lise Getoor.
        Proc. 2nd ACM SIGKDD Workshop on Social Network Mining and Analysis (SNA-KDD), 2008.

  28. “On Estimating Path-Aggregates over Streaming Graphs”,
        with Sumit Ganguly.
        Proc. 17th International Symposium on Algorithms and Computations (ISAAC), 2006.

  29. “Bidirectional Fuzzy-Regression Model for Road-lines Detection”,
        with Arya Mazumdar, N R Pal.
        Proc. IEEE International Conference on Engineering of Intelligent Systems (ICEIS), 2006.