Also see DBLP, Google Scholar, or ACM's Digital Library.

Journal Publications:

  1. A Near-Optimal Algorithm for Computing the Entropy of a Stream
    Submitted: ACM Transactions on Algorithms (with A. Chakrabarti and G. Cormode).
  2. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
    Submitted: IEEE Transactions on Information Theory (with O. Milenkovic)
  3. Estimating Statistical Aggregates on Probabilistic Data Streams
    To appear: ACM Transactions on Database Systems (with T. S. Jayram, S. Muthukrishnan, and E. Vee)
  4. Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
    To appear: SIAM Journal of Computing (with S. Guha)
  5. Graph Distances in the Data Stream Model
    To appear: SIAM Journal of Computing (with J. Feigenbaum, S. Kannan, S. Suri, and J. Zhang)
  6. Sub-linear Estimation of Entropy and Information Distances
    To appear: ACM Transactions on Algorithms (with S. Guha and S. Venkatasubramanian)
  7. Sketching Information Divergences
    Journal of Machine Learning, 72 (2008), no. 1-2, pg. 5-19 (with S. Guha and P. Indyk)
  8. Distance distribution of binary codes and the error probability of decoding
    IEEE Transactions on Information Theory, 51 (2005), no. 12, pg. 4237-4246. (with A. Barg)
  9. On Graph Problems in a Semi-Streaming Model
    Theoretical Computer Science, 348 (2005), no. 2-3, pg. 207-216 (with J. Feigenbaum, S. Kannan, S. Suri and J. Zhang)

Conference Publications (N.B. Links point to journal/extended versions if appropriate):

  1. Finding Metric Structure in Information Theoretic Clustering
    COLT 2008 (with K. Chaudhuri)
  2. Tight Lower Bounds for Multi-Pass Stream Computation via Pass Elimination
    ICALP 2008 (with S. Guha)
  3. Approximation Algorithms for Clustering Uncertain Data
    PODS 2008 (with G. Cormode)
  4. Robust Lower Bounds for Communication and Stream Computation
    STOC 2008 (with A. Chakrabarti and G. Cormode)
  5. Sorting and Selection with Random Costs
    LATIN 2008 (with S. Angelov and K. Kunal)
  6. Declaring Independence via the Sketching of Sketches
    SODA 2008 (with P. Indyk)
  7. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
    ITW 2007 (with O. Milenkovic)
  8. Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming
    ICALP 2007 (with S. Guha)
  9. Checking and Spot-Checking of Heaps
    ICALP 2007 (with M. Chu and S. Kannan)
  10. Sketching Information Divergences
    COLT 2007 (with S. Guha and P. Indyk)
    Invited to Special Issue of Machine Learning Journal
  11. Estimating Statistical Aggregates on Probabilistic Data Streams
    PODS 2007 (with T. S. Jayram, S. Muthukrishnan, and E. Vee)
    Invited to Special Issue of ACM Transactions on Database Systems
  12. Space-Efficient Sampling
    AISTATS 2007 (with S. Guha)
  13. Island Hopping and Path Colouring with Applications to WDM Network Design
    SODA 2007 (with F.B. Shepherd) Slides
  14. A Near-Optimal Algorithm for Computing the Entropy of a Stream
    SODA 2007 (with A. Chakrabarti and G. Cormode) Slides
  15. Spatial Scan Statistics: Approximations and Performance Study
    KDD 2006 (with D. Agarwal, J. Phillips, S. Venkatasubramanian and Z. Zhu)
  16. Approximate Quantiles and the Order of the Stream
    PODS 2006 (with S. Guha)
  17. Streaming and Sublinear Approximation of Entropy and Information Distances
    SODA 2006 (with S. Guha and S. Venkatasubramanian)
  18. More on Reconstructing Strings from Random Traces: Insertions and Deletions
    ISIT 2005 (with S. Kannan) Slides
  19. Approximating the Best-Fit Tree Under L_p Norms
    Approx 2005 (with B. Harb and S. Kannan) Slides
  20. Finding Matchings in the Streaming Model
    Approx 2005 Slides
  21. Graph Distances in the Streaming Model: The Value of Space
    SODA 2005. (with J. Feigenbaum, S. Kannan, S. Suri, and J. Zhang) Slides
  22. A Problem in Scheduling: Your Time Starts Now...
    FUN with Algorithms 2004
  23. List decoding of concatenated codes: improved performance estimates
    ISIT 2004 (with A. Barg) Slides
  24. On Graph Problems in a Semi-Streaming Model
    ICALP 2004 (with J. Feigenbaum, S. Kannan, S. Suri and J. Zhang)
    Invited to Special Issue of Theoretical Computer Science
  25. Reconstructing Strings from Random Traces
    SODA 2004 (with T. Batu, S. Kannan and S. Khanna)
  26. More on the Reliability Function of the Binary Symmetric Channel
    ISIT 2003 (with A. Barg) Slides
  27. Distance distribution of binary codes and the error probability of decoding
    WCC 2003 International Workshop on Coding and Cryptography (with A. Barg)
  28. Physical Modeling of Musical Instruments using Bond Graphs
    Brazilian Symposium on Computer Music 1999 (with E. Miranda and P. Gawthrop)
Other:
  1. The Oil Searching Problem
    Submitted (with K. Onak and R. Panigrahy)
  2. Better Bounds for Frequency Moments in Random-Order Streams
    Manuscript (with A. Andoni, K. Onak and R. Panigrahy)
  3. Graph Mining in Streams
    Entry for the Encyclopedia of Database Systems
  4. Processing Data Streams
    Ph.D. Thesis (Advisor: Sampath Kannan)
  5. Open Questions In Data Streams and Related Topics
    Questions arising at the IITK Workshop on Algorithms for Data Streams 2006.

Co-authors: Deepak Agarwal, Alexandr Andoni, Stan Angelov, Sasha Barg, Tugkan Batu, Amit Chakrabarti, Kamalika Chaudhuri Matthew Chu, Graham Cormode, Joan Feigenbaum, Peter Gawtrop, Sudipto Guha, Boulos Harb, Piotr Indyk, T. S. Jayram, Sampath Kannan, Sanjeev Khanna, Keshav Kunal, Olgica Milenkovic, Eduardo Miranda, S. Muthukrishnan , Krzysztof Onak, Rina Panigrahy, Jeff Phillips, Bruce Shepherd, Sid Suri, Erik Vee, Suresh Venkatasubramanian, Jian Zhang, and Zhengyuan Zhu.

NB: Since most of the papers above are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. See below for ACM's copyright notice.

Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.