See also Google Scholar and DBLP.

Journal Publications:

  1. AUTOMAN: A Platform for Integrating Human-Based and Digital Computation
    Communications of the ACM 59(6): 102-109 2016 (with D. Barowy, C. Curtsinger, and E. Berger).
  2. Robust Lower Bounds for Communication and Stream Computation
    Theory of Computing 2016 (with A. Chakrabarti and G. Cormode)
  3. The matrix mechanism: optimizing linear counting queries under differential privacy
    VLDB Journal 2015 (with C. Li, G. Miklau, M. Hay, and V. Rastogi)
  4. Space-Efficient Estimation of Statistics over Sub-Sampled Streams
    Algorithmica, 2015. (with A. Pavan, S. Tirthapura, and D. Woodruff)
  5. Annotations in Data Streams
    ACM Transactions on Algorithms, 11 (2014), no. 1, pg. 1-30 (with A. Chakrabarti, G. Cormode, and J. Thaler).
  6. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
    SIAM Journal of Computing, 42 (2013), no. 1, pg. 61–83. (with A. Chakrabarti, G. Cormode, and R. Kondapally)
  7. SCALLA: A Platform for Scalable One-Pass Analytics using MapReduce
    ACM Trans. Database Syst, 37 (2012), no. 4, pg. 1-43 (with B. Li, E. Mazur, Y. Diao, and P. Shenoy)
  8. CLARO: Modeling and Processing Uncertain Data Streams
    VLDB Journal, 21 (2012), no. 5, pg. 651-676 (with T. Tran, L. Peng, Y. Diao, and A. Liu)
  9. 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)
  10. On the Hardness of Approximating Stopping and Trapping Sets
    IEEE Transactions on Information Theory, 56 (2010), no. 4, pg. 1640-1650 (with O. Milenkovic)
  11. 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)
  12. Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
    SIAM Journal of Computing, 38 (2009), no. 5, 2044-2059 (with S. Guha)
  13. 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)
  14. 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)
  15. Sketching Information Divergences
    Journal of Machine Learning, 72 (2008), no. 1-2, pg. 5-19 (with S. Guha and P. Indyk)
  16. 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)
  17. 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. Storage Capacity as an Information-Theoretic Analogue of Vertex Cover
    ISIT 2017 (with A. Mazumdar and S. Vorotnikova)
  2. Better Approximation of The Streaming Maximum Coverage Problem
    ICDT 2017 (with H. Vu)
  3. Planar Matchings in Streams Revisited
    APPROX 2016 (with S. Vorotnikova)
  4. Stochastic Streams: Sample Complexity vs. Space Complexity
    ESA 2016 (with M. Crouch, G. Valiant, and D. Woodruff)
  5. Better Algorithms for Counting Triangles in Data Streams
    PODS 2016 (with S. Vorotnikova and H. Vu)
  6. Sketching, Embedding, and Dimensionality Reduction for Information Spaces
    AISTATS 2016 (with A. Abdullah, R. Kumar, S. Vassilvitskii, and S. Venkatasubramanian)
  7. Kernelization via Sampling with Applications to Dynamic Graph Streams
    SODA 2016 (with R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, M. Monemizadeh, and S. Vorotnikova)
  8. Run Generation Revisited: What Goes Up May or May Not Come Down
    ISAAC 2015 (with M. Bender, S. McCauley, S. Singh, and H. T. Vu)
  9. Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution
    ICDM 2015 (with O. Simpson and C. Seshadhri)
  10. Densest Subgraph in Dynamic Graph Streams
    MFCS 2015 (with D. Tench, S. Vorotnikova, and H. Vu)
  11. Correlation Clustering in Data Streams
    ICML 2015 (with K. Ahn, G. Cormode, S. Guha, and A. Wirth)
  12. Evaluating Bayesian Networks via Data Streams
    COCOON 2015 (with H. T. Vu)
  13. Vertex and Hyperedge Connectivity in Dynamic Graph Streams
    PODS 2015 (with S. Guha and D. Tench)
  14. Verifiable Stream Computation and Arthur–Merlin Communication
    CCC 2015 (with A. Chakrabarti, G. Cormode, J. Thaler, and S. Venkatasubramanian)
  15. Trace Reconstruction Revisited
    ESA 2014 (with E. Price and S. Vorotnikova)
  16. Dynamic Graphs in the Sliding-Window Model
    ESA 2013 (with M. Crouch and D. Stubbs)
  17. Sketching Earth-Mover Distance on Graph Metrics
    APPROX 2013 (with D. Stubbs)
  18. Spectral Sparsification of Dynamic Graph Streams
    APPROX 2013 (with K. Ahn and S. Guha)
  19. Efficient Nearest-Neighbor Search in the Probability Simplex
    ICTIR 2013 (with K. Krstovski, D. Smith, and H. Wallach)
  20. Homomorphic Fingerprints under Misalignments
    STOC 2013 (with A. Andoni, A. Goldberger, and E. Porat)
  21. AUTOMAN: A Platform for Integrating Human-Based and Digital Computation
    OOPSLA 2012 (with D. Barowy, C. Curtsinger, and E. Berger). [Press Coverage].
  22. Approximate Principal Direction Trees
    ICML 2012 (with M. McCartin-Lim and R. Wang)
  23. Space-Efficient Estimation of Statistics over Sub-Sampled Streams
    PODS 2012 (with A. Pavan, S. Tirthapura, and D. Woodruff)
  24. Graph Sketches: Sparsfiers, Spanners, and Subgraphs
    PODS 2012 (with K. Ahn and S. Guha)
  25. Analyzing Graph Structure via Linear Measurements
    SODA 2012 (with K. Ahn and S. Guha)
  26. The Shifting Sands Algorithm
    SODA 2012 (with P. Valiant)
  27. Periodicity and Cyclic Shifts via Linear Sketches
    APPROX 2011 (with M. Crouch)
  28. A Platform for Scalable One-pass Analytics using MapReduce
    SIGMOD 2011 (with B. Li, E. Mazur, Y. Diao, and P. Shenoy)
  29. Polynomial Fitting of Data Streams with Applications to Codeword Testing
    STACS 2011 (with A. Rudra and S. Uurtamo)
  30. Fast Query Expansion Using Approximations of Relevance Models
    CIKM 2010 (with M. Cartright, J. Allan, and V. Lavrenko)
  31. The Limits of Two-Party Differential Privacy
    FOCS 2010 (with I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan)
  32. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
    FOCS 2010 (with A. Chakrabarti, G. Cormode, and R. Kondapally)
  33. Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations
    VLDB 2010 (with T. Tran, Y. Diao, L. Peng, and A. Liu)
  34. Optimizing Linear Counting Queries Under Differential Privacy
    PODS 2010 (with C. Li, M. Hay, V. Rastogi, and G. Miklau)
  35. Space-Efficient Estimation of Robust Statistics and Distribution Testing
    ICS 2010 (with S. Chien and K. Ligett)
  36. Probabilistic Histograms for Probabilistic Data
    VLDB 2009 (with G. Cormode, A. Deligiannakis, and M. Garofalakis)
  37. The Oil Searching Problem
    ESA 2009 (with K. Onak and R. Panigrahy)
  38. Annotations in Data Streams
    ICALP 2009 (with A. Chakrabarti and G. Cormode).
  39. Sampling to Estimate Conditional Functional Dependencies
    SIGMOD 2009 (with G. Cormode, L. Golab, F. Korn, D. Srivastava, and X. Zhang)
  40. Finding Metric Structure in Information Theoretic Clustering
    COLT 2008 (with K. Chaudhuri)
  41. Tight Lower Bounds for Multi-Pass Stream Computation via Pass Elimination
    ICALP 2008 (with S. Guha)
  42. Approximation Algorithms for Clustering Uncertain Data
    PODS 2008 (with G. Cormode)
  43. Robust Lower Bounds for Communication and Stream Computation
    STOC 2008 (with A. Chakrabarti and G. Cormode) Slides
  44. Sorting and Selection with Random Costs
    LATIN 2008 (with S. Angelov and K. Kunal)
  45. Declaring Independence via the Sketching of Sketches
    SODA 2008 (with P. Indyk)
  46. On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
    ITW 2007 (with O. Milenkovic)
  47. Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming
    ICALP 2007 (with S. Guha) Slides
  48. Checking and Spot-Checking of Heaps
    ICALP 2007 (with M. Chu and S. Kannan) Slides
  49. Sketching Information Divergences
    COLT 2007 (with S. Guha and P. Indyk)
    Invited to Special Issue of Machine Learning Journal
  50. 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
  51. Space-Efficient Sampling
    AISTATS 2007 (with S. Guha)
  52. Island Hopping and Path Colouring with Applications to WDM Network Design
    SODA 2007 (with F.B. Shepherd) Slides
  53. A Near-Optimal Algorithm for Computing the Entropy of a Stream
    SODA 2007 (with A. Chakrabarti and G. Cormode) Slides
  54. Spatial Scan Statistics: Approximations and Performance Study
    KDD 2006 (with D. Agarwal, J. Phillips, S. Venkatasubramanian, and Z. Zhu)
  55. Approximate Quantiles and the Order of the Stream
    PODS 2006 (with S. Guha)
  56. Streaming and Sublinear Approximation of Entropy and Information Distances
    SODA 2006 (with S. Guha and S. Venkatasubramanian)
  57. More on Reconstructing Strings from Random Traces: Insertions and Deletions
    ISIT 2005 (with S. Kannan) Slides
  58. Approximating the Best-Fit Tree Under L_p Norms
    APPROX 2005 (with B. Harb and S. Kannan) Slides
  59. Finding Matchings in the Streaming Model
    APPROX 2005 Slides
  60. Graph Distances in the Streaming Model: The Value of Space
    SODA 2005. (with J. Feigenbaum, S. Kannan, S. Suri, and J. Zhang) Slides
  61. A Problem in Scheduling: Your Time Starts Now...
    FUN with Algorithms 2004
  62. List decoding of concatenated codes: improved performance estimates
    ISIT 2004 (with A. Barg) Slides
  63. 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
  64. Reconstructing Strings from Random Traces
    SODA 2004 (with T. Batu, S. Kannan, and S. Khanna)
  65. More on the Reliability Function of the Binary Symmetric Channel
    ISIT 2003 (with A. Barg) Slides
  66. Distance distribution of binary codes and the error probability of decoding
    WCC 2003 International Workshop on Coding and Cryptography (with A. Barg)
  67. 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. Graph Stream Algorithms: A Survey
    SIGMOD Record
  2. Towards a Theory of Homomorphic Compression
    Invited Session at CiE 2013
  3. Better Bounds for Frequency Moments in Random-Order Streams
    Manuscript (with A. Andoni, K. Onak and R. Panigrahy)
  4. Graph Mining in Streams
    Entry for the Encyclopedia of Database Systems
  5. Processing Data Streams
    Ph.D. Thesis (Advisor: Sampath Kannan) Slides
  6. Open Questions In Data Streams and Related Topics
    Questions arising at the IITK Workshop on Algorithms for Data Streams 2006.
  7. 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 20xy 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.