See also Google Scholar and DBLP.

Journal Publications:

  1. CLARO: Modeling and Processing Uncertain Data Streams
    VLDB Journal (with T. Tran, L. Peng, Y. Diao, and A. Liu).
  2. A Near-Optimal Algorithm for Computing the Entropy of a Stream
    ACM Transactions on Algorithms, 6 (2010), no. 3, pg. 1-21 (with A. Chakrabarti and G. Cormode).
  3. On the Hardness of Approximating Stopping and Trapping Sets
    IEEE Transactions on Information Theory, 56 (2010), no. 4, pg. 1640-1650 (with O. Milenkovic)
  4. Sub-linear Estimation of Entropy and Information Distances
    ACM Transactions on Algorithms, 5 (2009), no. 4, pg. 1-16. (with S. Guha and S. Venkatasubramanian)
  5. Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
    SIAM Journal of Computing, 38 (2009), no. 5, 2044-2059 (with S. Guha)
  6. Graph Distances in the Data Stream Model
    SIAM Journal of Computing, 38 (2008), no. 5, pg. 1709-1727 (with J. Feigenbaum, S. Kannan, S. Suri, and J. Zhang)
  7. Estimating Statistical Aggregates on Probabilistic Data Streams
    ACM Trans. Database Syst, 33 (2008), no. 4, pg. 1-30 (with T. S. Jayram, S. Muthukrishnan, and E. Vee)
  8. Sketching Information Divergences
    Journal of Machine Learning, 72 (2008), no. 1-2, pg. 5-19 (with S. Guha and P. Indyk)
  9. 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)
  10. 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. Analyzing Graph Structure via Linear Measurements
    SODA 2012 (with K. Ahn and S. Guha)
  2. The Shifting Sands Algorithm
    SODA 2012 (with P. Valiant)
  3. Periodicity and Cyclic Shifts via Linear Sketches
    APPROX 2011 (with M. Crouch)
  4. A Platform for Scalable One-pass Analytics using MapReduce
    SIGMOD 2011 (with B. Li, E. Mazur, Y. Diao, and P. Shenoy)
  5. Polynomial Fitting of Data Streams with Applications to Codeword Testing
    STACS 2011 (with A. Rudra and S. Uurtamo)
  6. Fast Query Expansion Using Approximations of Relevance Models
    CIKM 2010 (with M. Cartright, J. Allan, and V. Lavrenko)
  7. The Limits of Two-Party Differential Privacy
    FOCS 2010 (with I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan)
  8. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
    FOCS 2010 (with A. Chakrabarti, G. Cormode, and R. Kondapally)
  9. Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations
    VLDB 2010 (with T. Tran, Y. Diao, L. Peng, and A. Liu)
  10. Optimizing Linear Counting Queries Under Differential Privacy
    PODS 2010 (with C. Li, M. Hay, V. Rastogi, and G. Miklau)
  11. Space-Efficient Estimation of Robust Statistics and Distribution Testing
    ICS 2010 (with S. Chien and K. Ligett)
  12. Probabilistic Histograms for Probabilistic Data
    VLDB 2009 (with G. Cormode, A. Deligiannakis, and M. Garofalakis)
  13. The Oil Searching Problem
    ESA 2009 (with K. Onak and R. Panigrahy)
  14. Annotations in Data Streams
    ICALP 2009 (with A. Chakrabarti and G. Cormode).
  15. Sampling to Estimate Conditional Functional Dependencies
    SIGMOD 2009 (with G. Cormode, L. Golab, F. Korn, D. Srivastava, and X. Zhang)
  16. Finding Metric Structure in Information Theoretic Clustering
    COLT 2008 (with K. Chaudhuri)
  17. Tight Lower Bounds for Multi-Pass Stream Computation via Pass Elimination
    ICALP 2008 (with S. Guha)
  18. Approximation Algorithms for Clustering Uncertain Data
    PODS 2008 (with G. Cormode)
  19. Robust Lower Bounds for Communication and Stream Computation
    STOC 2008 (with A. Chakrabarti and G. Cormode) Slides
  20. Sorting and Selection with Random Costs
    LATIN 2008 (with S. Angelov and K. Kunal)
  21. Declaring Independence via the Sketching of Sketches
    SODA 2008 (with P. Indyk)
  22. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
    ITW 2007 (with O. Milenkovic)
  23. Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming
    ICALP 2007 (with S. Guha) Slides
  24. Checking and Spot-Checking of Heaps
    ICALP 2007 (with M. Chu and S. Kannan) Slides
  25. Sketching Information Divergences
    COLT 2007 (with S. Guha and P. Indyk)
    Invited to Special Issue of Machine Learning Journal
  26. 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
  27. Space-Efficient Sampling
    AISTATS 2007 (with S. Guha)
  28. Island Hopping and Path Colouring with Applications to WDM Network Design
    SODA 2007 (with F.B. Shepherd) Slides
  29. A Near-Optimal Algorithm for Computing the Entropy of a Stream
    SODA 2007 (with A. Chakrabarti and G. Cormode) Slides
  30. Spatial Scan Statistics: Approximations and Performance Study
    KDD 2006 (with D. Agarwal, J. Phillips, S. Venkatasubramanian, and Z. Zhu)
  31. Approximate Quantiles and the Order of the Stream
    PODS 2006 (with S. Guha)
  32. Streaming and Sublinear Approximation of Entropy and Information Distances
    SODA 2006 (with S. Guha and S. Venkatasubramanian)
  33. More on Reconstructing Strings from Random Traces: Insertions and Deletions
    ISIT 2005 (with S. Kannan) Slides
  34. Approximating the Best-Fit Tree Under L_p Norms
    Approx 2005 (with B. Harb and S. Kannan) Slides
  35. Finding Matchings in the Streaming Model
    Approx 2005 Slides
  36. Graph Distances in the Streaming Model: The Value of Space
    SODA 2005. (with J. Feigenbaum, S. Kannan, S. Suri, and J. Zhang) Slides
  37. A Problem in Scheduling: Your Time Starts Now...
    FUN with Algorithms 2004
  38. List decoding of concatenated codes: improved performance estimates
    ISIT 2004 (with A. Barg) Slides
  39. 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
  40. Reconstructing Strings from Random Traces
    SODA 2004 (with T. Batu, S. Kannan, and S. Khanna)
  41. More on the Reliability Function of the Binary Symmetric Channel
    ISIT 2003 (with A. Barg) Slides
  42. Distance distribution of binary codes and the error probability of decoding
    WCC 2003 International Workshop on Coding and Cryptography (with A. Barg)
  43. Physical Modeling of Musical Instruments using Bond Graphs
    Brazilian Symposium on Computer Music 1999 (with E. Miranda and P. Gawthrop)
Manuscripts, Invited Papers, etc.:
  1. Better Bounds for Frequency Moments in Random-Order Streams
    Manuscript (with A. Andoni, K. Onak and R. Panigrahy)
  2. Graph Mining in Streams
    Entry for the Encyclopedia of Database Systems
  3. Processing Data Streams
    Ph.D. Thesis (Advisor: Sampath Kannan)
  4. Open Questions In Data Streams and Related Topics
    Questions arising at the IITK Workshop on Algorithms for Data Streams 2006.
  5. Open Questions In Data Streams, Property Testing, and Related Topics
    Questions arising at Sublinear Algorithms 2011 and IITK Workshop on Algorithms for Data Streams 2009 (with P. Indyk, I. Newman, and K. Onak)

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 200x 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.