See also Google Scholar and DBLP.
Journal Publications:
- Trace Reconstruction: Generalized and Parameterized
IEEE Transactions on Information Theory (with A. Krishnamurthy, A. Mazumdar, S. Pal) - Correlation Clustering in Data Streams
Algorithmica (with K. Ahn, G. Cormode, S. Guha, A. Wirth) - Verifiable Stream Computation and Arthur–Merlin Communication
SIAM Journal of Computing, 2019 (with A. Chakrabarti, G. Cormode, J. Thaler, S. Venkatasubramanian) - Storage Capacity as an Information-Theoretic Analogue of Vertex Cover
IEEE Transactions on Information Theory, 2019 (with A. Mazumdar, S. Vorotnikova) - Structural Results on Matching Estimation with Applications to Streaming.
Algorithmica, 2019 (with M. Bury, E. Grigorescu, M. Monemizadeh, C. Schwiegelshohn, S. Vorotnikova) - Better Approximation of The Streaming Maximum Coverage Problem
Theory of Computer Systems 2019 (with H. Vu) - AUTOMAN: A Platform for Integrating Human-Based and Digital Computation
Communications of the ACM 59(6): 102-109 2016 (with D. Barowy, C. Curtsinger, E. Berger) - Robust Lower Bounds for Communication and Stream Computation
Theory of Computing 2016 (with A. Chakrabarti G. Cormode) - The matrix mechanism: optimizing linear counting queries under differential privacy
VLDB Journal 2015 (with C. Li, G. Miklau, M. Hay, V. Rastogi) - Space-Efficient Estimation of Statistics over Sub-Sampled Streams
Algorithmica, 2015. (with A. Pavan, S. Tirthapura, D. Woodruff) - Annotations in Data Streams
ACM Transactions on Algorithms, 11 (2014), no. 1, pg. 1-30 (with A. Chakrabarti, G. Cormode, J. Thaler) - 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, R. Kondapally) - 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, P. Shenoy) - CLARO: Modeling and Processing Uncertain Data Streams
VLDB Journal, 21 (2012), no. 5, pg. 651-676 (with T. Tran, L. Peng, Y. Diao, A. Liu) - 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, G. Cormode) - On the Hardness of Approximating Stopping
and Trapping Sets
IEEE Transactions on Information Theory, 56 (2010), no. 4, pg. 1640-1650 (with O. Milenkovic) -
Sub-linear Estimation of Entropy and Information Distances
ACM Transactions on Algorithms, 5 (2009), no. 4, pg. 1-16. (with S. Guha, S. Venkatasubramanian) -
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
SIAM Journal of Computing, 38 (2009), no. 5, 2044-2059 (with S. Guha) -
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, J. Zhang) - Estimating Statistical Aggregates on Probabilistic Data Streams
ACM Trans. Database Syst, 33 (2008), no. 4, pg. 1-30 (with T. S. Jayram, S. Muthukrishnan, E. Vee) - Sketching Information Divergences
Journal of Machine Learning, 72 (2008), no. 1-2, pg. 5-19 (with S. Guha, P. Indyk) - 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) -
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, J. Zhang)
Conference Publications (N.B. Links point to journal/extended versions if appropriate):
- Estimation of Entropy in Constant Space with Improved Sample Complexity
ISIT 2024 (with R. Sengupta) - Tight Approximations for Graphical House Allocation
AAMAS 2024 (with H. Hosseini, R. Sengupta, R. Vaish and V. Viswanathan) - Estimation of Entropy in Constant Space with Improved Sample Complexity
NeurIPS 2022 (with M. Aliakbarpour, J. Nelson, E. Waingarten) - Estimation of Entropy in Constant Space with Improved Sample Complexity
NeurIPS 2022 (with M. Aliakbarpour, J. Nelson, E. Waingarten) - Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests
CML4Impact 2022 (NeurIPS Workshop) (with E. Cai, D. Jensen) - Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries
ESA 2022 (with R. Addanki, C. Musco) - Graph Reconstruction from Random Subgraphs
ICALP 2022 (with R. Sengupta) - Improved Approximation and Scalability for Fair Max-Min Diversification
ICDT 2022 (with R. Addanki, A. Meliou, Z. Moumoulidou) - PredictRoute: A Network Path Prediction Toolkit.
Sigmetrics 2021 (with R. Singh, D. Tench, P. Gill) - Cluster Trellis: Data Structures & Algorithms for Exact Inference in Hierarchical Clustering
AISTATS 2021 (with C. Greenberg, S. Macaluso, N. Monath, J. Lee, P. Flaherty, K. Cranmer, A. McCallum) - Intervention Efficient Algorithms for Approximate Learning of Causal Graphs
ALT 2021 (with R. Addanki, C. Musco) - Diverse Data Selection under Fairness Constraints
ICDT 2021 (with Z. Moumoulidou, A. Meliou) - Maximum Coverage in the Data Stream Model: Parameterized and Generalized
ICDT 2021 (with D. Tench, H. Vu) - Cache me Outside: A New Look at DNS Cache Probing
PAM 2021 (with A. Niaki, W. Marczak, S. Farhoodi, P. Gill, N. Weaver) - Efficient Intervention Design for Causal Discovery with Latents
ICML 2020 (with R. Addanki, S. Kasiviswanathan, C. Musco) - Triangle and Four Cycle Counting in the Data Stream Model
PODS 2020 (with S. Vorotnikova) - Algebraic and Analytic Approaches for Parameter Learning in Mixture Models
ALT 2020 (with A. Krishnamurthy, A. Mazumdar, S. Pal) - Vertex Ordering Problems in Directed Graph Streams
SODA 2020 (with A. Chakrabarti, P. Ghosh, S. Vorotnikova) - Sample Complexity of Learning Mixture of Sparse Linear Regressions
NeurIPS 2019 (with A. Krishnamurthy, A. Mazumdar, S. Pal) - Trace Reconstruction: Generalized and Parameterized
ESA 2019 (with A. Krishnamurthy, A. Mazumdar, S. Pal) - Mesh: Compacting Memory Management for C/C++ Applications
PLDI 2019 (with B. Powers, D. Tench, E. Berger) - The Complexity of Counting Cycles in the Adjacency List Streaming Model
PODS 2019 (with J. Kallaugher, E. Price, S. Vorotnikova) - Compact Representation of Uncertainty In Clustering
NeurIPS 2018 (with C. Greenberg, A. Kobren, N. Monath, P. Flaherty, A. McCallum) - Connect the Dots to Prove It: A Novel Way to Learn Proof Construction
SIGCSE 2018 (with M. McCartin-Lim, B. Woolf) - A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs
SOSA 2018 (with S. Vorotnikova) - Storage Capacity as an Information-Theoretic Analogue of Vertex Cover
ISIT 2017 (with A. Mazumdar, S. Vorotnikova) - Better Approximation of The Streaming Maximum Coverage Problem
ICDT 2017 (with H. Vu) - Planar Matchings in Streams Revisited
APPROX 2016 (with S. Vorotnikova) - Stochastic Streams: Sample Complexity vs. Space Complexity
ESA 2016 (with M. Crouch, G. Valiant, D. Woodruff) - Better Algorithms for Counting Triangles in Data Streams
PODS 2016 (with S. Vorotnikova, H. Vu) - Sketching, Embedding, and Dimensionality Reduction for Information Spaces
AISTATS 2016 (with A. Abdullah, R. Kumar, S. Vassilvitskii, S. Venkatasubramanian) - Kernelization via Sampling with Applications to Dynamic Graph Streams
SODA 2016 (with R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, M. Monemizadeh, S. Vorotnikova) - Run Generation Revisited: What Goes Up May or May Not Come Down
ISAAC 2015 (with M. Bender, S. McCauley, S. Singh, H. T. Vu) - Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution
ICDM 2015 (with O. Simpson, C. Seshadhri) - Densest Subgraph in Dynamic Graph Streams
MFCS 2015 (with D. Tench, S. Vorotnikova, H. Vu) - Correlation Clustering in Data Streams
ICML 2015 (with K. Ahn, G. Cormode, S. Guha, A. Wirth) - Evaluating Bayesian Networks via Data Streams
COCOON 2015 (with H. T. Vu) - Vertex and Hyperedge Connectivity in Dynamic Graph Streams
PODS 2015 (with S. Guha, D. Tench) - Verifiable Stream Computation and Arthur–Merlin Communication
CCC 2015 (with A. Chakrabarti, G. Cormode, J. Thaler, S. Venkatasubramanian) - Trace Reconstruction Revisited
ESA 2014 (with E. Price, S. Vorotnikova) - Dynamic Graphs in the Sliding-Window Model
ESA 2013 (with M. Crouch, D. Stubbs) - Sketching Earth-Mover Distance on Graph Metrics
APPROX 2013 (with D. Stubbs) - Spectral Sparsification of Dynamic Graph Streams
APPROX 2013 (with K. Ahn, S. Guha) - Efficient Nearest-Neighbor Search in the Probability Simplex
ICTIR 2013 (with K. Krstovski, D. Smith, H. Wallach) - Homomorphic Fingerprints under Misalignments
STOC 2013 (with A. Andoni, A. Goldberger, E. Porat) - AUTOMAN: A Platform for Integrating Human-Based and Digital Computation
OOPSLA 2012 (with D. Barowy, C. Curtsinger, E. Berger). [Press Coverage]. - Approximate Principal Direction Trees
ICML 2012 (with M. McCartin-Lim, R. Wang) - Space-Efficient Estimation of Statistics over Sub-Sampled Streams
PODS 2012 (with A. Pavan, S. Tirthapura, D. Woodruff) - Graph Sketches: Sparsfiers, Spanners, and Subgraphs
PODS 2012 (with K. Ahn, S. Guha) - Analyzing Graph Structure via Linear Measurements
SODA 2012 (with K. Ahn, S. Guha) - The Shifting Sands Algorithm
SODA 2012 (with P. Valiant) - Periodicity and Cyclic Shifts via Linear Sketches
APPROX 2011 (with M. Crouch) - A Platform for Scalable One-pass Analytics using MapReduce
SIGMOD 2011 (with B. Li, E. Mazur, Y. Diao, P. Shenoy) - Polynomial Fitting of Data Streams with Applications to Codeword Testing
STACS 2011 (with A. Rudra, S. Uurtamo) - Fast Query Expansion Using Approximations of Relevance Models
CIKM 2010 (with M. Cartright, J. Allan, V. Lavrenko) - The Limits of Two-Party Differential Privacy
FOCS 2010 (with I. Mironov, T. Pitassi, O. Reingold, K. Talwar, S. Vadhan) - Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
FOCS 2010 (with A. Chakrabarti, G. Cormode, R. Kondapally) - Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations
VLDB 2010 (with T. Tran, Y. Diao, L. Peng, A. Liu) - Optimizing Linear Counting Queries Under Differential Privacy
PODS 2010 (with C. Li, M. Hay, V. Rastogi, G. Miklau) - Space-Efficient Estimation of Robust Statistics and Distribution Testing
ICS 2010 (with S. Chien, K. Ligett) - Probabilistic Histograms for Probabilistic Data
VLDB 2009 (with G. Cormode, A. Deligiannakis, M. Garofalakis) - The Oil Searching Problem
ESA 2009 (with K. Onak, R. Panigrahy) - Annotations in Data Streams
ICALP 2009 (with A. Chakrabarti, G. Cormode). - Sampling to Estimate Conditional Functional Dependencies
SIGMOD 2009 (with G. Cormode, L. Golab, F. Korn, D. Srivastava, X. Zhang) - Finding Metric Structure in Information Theoretic Clustering
COLT 2008 (with K. Chaudhuri) - Tight Lower Bounds for Multi-Pass Stream Computation via Pass Elimination
ICALP 2008 (with S. Guha) - Approximation Algorithms for Clustering Uncertain Data
PODS 2008 (with G. Cormode) - Robust Lower Bounds for Communication and Stream Computation
STOC 2008 (with A. Chakrabarti, G. Cormode) Slides - Sorting and Selection with Random Costs
LATIN 2008 (with S. Angelov, K. Kunal) - Declaring Independence via the Sketching of Sketches
SODA 2008 (with P. Indyk)- On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
ITW 2007 (with O. Milenkovic)- Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming
ICALP 2007 (with S. Guha) Slides- Checking and Spot-Checking of Heaps
ICALP 2007 (with M. Chu, S. Kannan) Slides- Sketching Information Divergences
COLT 2007 (with S. Guha, P. Indyk)
Invited to Special Issue of Machine Learning Journal- Estimating Statistical Aggregates on Probabilistic Data Streams
PODS 2007 (with T. S. Jayram, S. Muthukrishnan, E. Vee)
Invited to Special Issue of ACM Transactions on Database Systems- Space-Efficient Sampling
AISTATS 2007 (with S. Guha)- Island Hopping and Path Colouring with Applications to WDM Network Design
SODA 2007 (with F.B. Shepherd) Slides- A Near-Optimal Algorithm for Computing the Entropy of a Stream
SODA 2007 (with A. Chakrabarti, G. Cormode) Slides- Spatial Scan Statistics: Approximations and Performance Study
KDD 2006 (with D. Agarwal, J. Phillips, S. Venkatasubramanian, Z. Zhu)- Approximate Quantiles and the Order of the Stream
PODS 2006 (with S. Guha)- Streaming and Sublinear Approximation of Entropy and Information Distances
SODA 2006 (with S. Guha, S. Venkatasubramanian)- More on Reconstructing Strings from Random Traces: Insertions and Deletions
ISIT 2005 (with S. Kannan) Slides- Approximating the Best-Fit Tree Under L_p Norms
APPROX 2005 (with B. Harb, S. Kannan) Slides- Finding Matchings in the Streaming Model
APPROX 2005 Slides- Graph Distances in the Streaming Model: The Value of Space
SODA 2005. (with J. Feigenbaum, S. Kannan, S. Suri, J. Zhang) Slides- A Problem in Scheduling: Your Time Starts Now...
FUN with Algorithms 2004- List decoding of concatenated codes: improved performance estimates
ISIT 2004 (with A. Barg) Slides- On Graph Problems in a Semi-Streaming Model
ICALP 2004 (with J. Feigenbaum, S. Kannan, S. Suri, J. Zhang)
Invited to Special Issue of Theoretical Computer Science- Reconstructing Strings from Random Traces
SODA 2004 (with T. Batu, S. Kannan, S. Khanna)- More on the Reliability Function of the Binary Symmetric Channel
ISIT 2003 (with A. Barg) Slides- Distance distribution of binary codes and the error probability of decoding
WCC 2003 International Workshop on Coding and Cryptography (with A. Barg)- Physical Modeling of Musical Instruments using Bond Graphs
Brazilian Symposium on Computer Music 1999 (with E. Miranda, P. Gawthrop) - On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
- Graph Stream Algorithms: A Survey
SIGMOD Record - Graph Sketching and Streaming:
New Approaches for Analyzing Massive Graphs
CSR 2017 - Towards a Theory of Homomorphic Compression
Invited Session at CiE 2013 - Better Bounds for Frequency Moments in Random-Order Streams
Manuscript (with A. Andoni, K. Onak, R. Panigrahy) -
Graph Mining in Streams
Entry for the Encyclopedia of Database Systems -
Processing Data Streams
Ph.D. Thesis (Advisor: Sampath Kannan) Slides - Open Questions In Data Streams and Related Topics
Questions arising at the IITK Workshop on Algorithms for Data Streams 2006. - 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, 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.