Andrew McGregor

Rik Sengupta

Proceedings of the IEEE International Symposium on Information Theory, 2024

Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model.

[BibT_eX]

[DOI]

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams.

[BibT_eX]

[DOI]

Anthony Wirth

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Tight Approximations for Graphical House Allocation.

[BibT_eX]

[DOI]

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, 2024

2022

Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests.

[BibT_eX]

[DOI]

Erica Cai

David D. Jensen

CoRR, 2022

Estimation of Entropy in Constant Space with Improved Sample Complexity.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Improved Approximation and Scalability for Fair Max-Min Diversification.

[BibT_eX]

[DOI]

Proceedings of the 25th International Conference on Database Theory, 2022

Graph Reconstruction from Random Subgraphs.

[BibT_eX]

[DOI]

Rik Sengupta

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries.

[BibT_eX]

[DOI]

Raghavendra Addanki

Cameron Musco

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Trace Reconstruction: Generalized and Parameterized.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Guest Editorial Special Issue: "From Deletion-Correction to Graph Reconstruction: In Memory of Vladimir I. Levenshtein".

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

PredictRoute: A Network Path Prediction Toolkit.

[BibT_eX]

[DOI]

Proc. ACM Meas. Anal. Comput. Syst., 2021

Correlation Clustering in Data Streams.

[BibT_eX]

[DOI]

Algorithmica, 2021

Cache Me Outside: A New Look at DNS Cache Probing.

[BibT_eX]

[DOI]

Proceedings of the Passive and Active Measurement - 22nd International Conference, 2021

Diverse Data Selection under Fairness Constraints.

[BibT_eX]

[DOI]

Zafeiria Moumoulidou

Alexandra Meliou

Proceedings of the 24th International Conference on Database Theory, 2021

Maximum Coverage in the Data Stream Model: Parameterized and Generalized.

[BibT_eX]

[DOI]

David Tench

Proceedings of the 24th International Conference on Database Theory, 2021

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs.

[BibT_eX]

[DOI]

Raghavendra Addanki

Cameron Musco

Proceedings of the Algorithmic Learning Theory, 2021

Cluster Trellis: Data Structures & Algorithms for Exact Inference in Hierarchical Clustering.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

Compact Representation of Uncertainty in Hierarchical Clustering.

[BibT_eX]

[DOI]

CoRR, 2020

Vertex Ordering Problems in Directed Graph Streams.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Triangle and Four Cycle Counting in the Data Stream Model.

[BibT_eX]

[DOI]

Shiva Prasad Kasiviswanathan

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Efficient Intervention Design for Causal Discovery with Latents.

[BibT_eX]

[DOI]

Raghavendra Addanki

Cameron Musco

Proceedings of the 37th International Conference on Machine Learning, 2020

Algebraic and Analytic Approaches for Parameter Learning in Mixture Models.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2020

2019

Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate.

[BibT_eX]

[DOI]

Arya Mazumdar

IEEE Trans. Inf. Theory, 2019

Verifiable Stream Computation and Arthur-Merlin Communication.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Better Streaming Algorithms for the Maximum Coverage Problem.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

Sample Complexity of Learning Mixtures of Sparse Linear Regressions.

[BibT_eX]

[DOI]

CoRR, 2019

Structural Results on Matching Estimation with Applications to Streaming.

[BibT_eX]

[DOI]

Algorithmica, 2019

The Complexity of Counting Cycles in the Adjacency List Streaming Model.

[BibT_eX]

[DOI]

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Mesh: compacting memory management for C/C++ applications.

[BibT_eX]

[DOI]

Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2019

Sample Complexity of Learning Mixture of Sparse Linear Regressions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Graph Mining on Streams.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs.

[BibT_eX]

[DOI]

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Connect the Dots to Prove It: A Novel Way to Learn Proof Construction.

[BibT_eX]

[DOI]

Mark McCartin-Lim

Beverly P. Woolf

Proceedings of the 49th ACM Technical Symposium on Computer Science Education, 2018

Compact Representation of Uncertainty in Clustering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

Storage capacity as an information-theoretic analogue of vertex cover.

[BibT_eX]

[DOI]

Arya Mazumdar

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Graph Sketching and Streaming: New Approaches for Analyzing Massive Graphs.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2017

2016

Graph Sketching.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012).

[BibT_eX]

[DOI]

Rahul Santhanam

SIAM J. Comput., 2016

A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs.

[BibT_eX]

[DOI]

CoRR, 2016

AutoMan: a platform for integrating human-based and digital computation.

[BibT_eX]

[DOI]

Commun. ACM, 2016

Space-Efficient Estimation of Statistics Over Sub-Sampled Streams.

[BibT_eX]

[DOI]

Algorithmica, 2016

Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.

[BibT_eX]

[DOI]

Rajesh Chitnis

Hossein Esfandiari

MohammadTaghi Hajiaghayi

Morteza Monemizadeh

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Better Algorithms for Counting Triangles in Data Streams.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Stochastic Streams: Sample Complexity vs. Space Complexity.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Planar Matching in Streams Revisited.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

Sketching, Embedding and Dimensionality Reduction in Information Theoretic Spaces.

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 2016

2015

The matrix mechanism: optimizing linear counting queries under differential privacy.

[BibT_eX]

[DOI]

VLDB J., 2015

Kernelization via Sampling with Applications to Dynamic Graph Streams.

[BibT_eX]

[DOI]

Rajesh Hemant Chitnis

Hossein Esfandiari

MohammadTaghi Hajiaghayi

Morteza Monemizadeh

CoRR, 2015

Sketching, Embedding, and Dimensionality Reduction for Information Spaces.

[BibT_eX]

[DOI]

CoRR, 2015

Vertex and Hyperedge Connectivity in Dynamic Graph Streams.

[BibT_eX]

[DOI]

David Tench

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Densest Subgraph in Dynamic Graph Streams.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Run Generation Revisited: What Goes Up May or May Not Come Down.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Catching the Head, Tail, and Everything in Between: A Streaming Algorithm for the Degree Distribution.

[BibT_eX]

[DOI]

Olivia Simpson

C. Seshadhri

Proceedings of the 2015 IEEE International Conference on Data Mining, 2015

Evaluating Bayesian Networks via Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

Graph stream algorithms: a survey.

[BibT_eX]

[DOI]

SIGMOD Rec., 2014

Algorithms for Large Scale Graphs (NII Shonan Meeting 2014-12).

[BibT_eX]

[DOI]

Gopal Pandurangan

Sergei Vassilvitskii

NII Shonan Meet. Rep., 2014

Trace Reconstruction Revisited.

[BibT_eX]

[DOI]

Eric Price

Proceedings of the Algorithms - ESA 2014, 2014

2013

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

On Interactivity in Arthur-Merlin Communication and Stream Computation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Homomorphic fingerprints under misalignments: sketching edit and shift distances.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient Nearest-Neighbor Search in the Probability Simplex.

[BibT_eX]

[DOI]

Proceedings of the International Conference on the Theory of Information Retrieval, 2013

Dynamic Graphs in the Sliding-Window Model.

[BibT_eX]

[DOI]

Michael S. Crouch

Daniel M. Stubbs

Proceedings of the Algorithms - ESA 2013, 2013

Towards a Theory of Homomorphic Compression.

[BibT_eX]

[DOI]

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

Sketching Earth-Mover Distance on Graph Metrics.

[BibT_eX]

[DOI]

Daniel M. Stubbs

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Spectral Sparsification in Dynamic Graph Streams.

[BibT_eX]

[DOI]

Kook Jin Ahn

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

CLARO: modeling and processing uncertain data streams.

[BibT_eX]

[DOI]

VLDB J., 2012

SCALLA: A Platform for Scalable One-Pass Analytics Using MapReduce.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2012

Graph Synopses, Sketches, and Streams: A Survey.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2012

Annotations in Data Streams.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

The shifting sands algorithm.

[BibT_eX]

[DOI]

Paul Valiant

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Analyzing graph structure via linear measurements.

[BibT_eX]

[DOI]

Kook Jin Ahn

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Graph sketches: sparsification, spanners, and subgraphs.

[BibT_eX]

[DOI]

Kook Jin Ahn

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Approximate Principal Direction Trees.

[BibT_eX]

[DOI]

Mark McCartin-Lim

Rui Wang

Proceedings of the 29th International Conference on Machine Learning, 2012

2011

The Limits of Two-Party Differential Privacy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Robust Lower Bounds for Communication and Stream Computation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Polynomial Fitting of Data Streams with Applications to Codeword Testing.

[BibT_eX]

[DOI]

Atri Rudra

Steve Uurtamo

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

A platform for scalable one-pass analytics using MapReduce.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2011

Periodicity and Cyclic Shifts via Linear Sketches.

[BibT_eX]

[DOI]

Michael S. Crouch

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

On the hardness of approximating stopping and trapping sets.

[BibT_eX]

[DOI]

Olgica Milenkovic

IEEE Trans. Inf. Theory, 2010

A near-optimal algorithm for estimating the entropy of a stream.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2010

Optimizing linear counting queries under differential privacy.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

Space-Efficient Estimation of Robust Statistics and Distribution Testing.

[BibT_eX]

[DOI]

Steve Chien

Katrina Ligett

Proceedings of the Innovations in Computer Science, 2010

Fast query expansion using approximations of relevance models.

[BibT_eX]

[DOI]

Proceedings of the 19th ACM Conference on Information and Knowledge Management, 2010

2009

Graph Mining on Streams.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Database Systems, 2009

Sublinear estimation of entropy and information distances.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Probabilistic Histograms for Probabilistic Data.

[BibT_eX]

[DOI]

Antonios Deligiannakis

Minos N. Garofalakis

Proc. VLDB Endow., 2009

Optimizing Histogram Queries under Differential Privacy

[BibT_eX]

[DOI]

CoRR, 2009

Estimating the confidence of conditional functional dependencies.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2009

Annotations in Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

The Oil Searching Problem.

[BibT_eX]

[DOI]

Krzysztof Onak

Rina Panigrahy

Proceedings of the Algorithms, 2009

2008

Estimating statistical aggregates on probabilistic data streams.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2008

Graph Distances in the Data-Stream Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Sketching information divergences.

[BibT_eX]

[DOI]

Piotr Indyk

Mach. Learn., 2008

Better Bounds for Frequency Moments in Random-Order Streams

[BibT_eX]

[DOI]

CoRR, 2008

Declaring independence via the sketching of sketches.

[BibT_eX]

[DOI]

Piotr Indyk

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Approximation algorithms for clustering uncertain data.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

Sorting and Selection with Random Costs.

[BibT_eX]

[DOI]

Stanislav Angelov

Keshav Kunal

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Finding Metric Structure in Information Theoretic Clustering.

[BibT_eX]

[DOI]

Kamalika Chaudhuri

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

Space-Efficient Sampling.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, 2007

On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes

[BibT_eX]

[DOI]

Olgica Milenkovic

CoRR, 2007

Island hopping and path colouring with applications to WDM network design.

[BibT_eX]

[DOI]

F. Bruce Shepherd

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

A near-optimal algorithm for computing the entropy of a stream.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Checking and Spot-Checking the Correctness of Priority Queues.

[BibT_eX]

[DOI]

Matthew Chu

Sampath Kannan

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

Estimating Aggregate Properties on Probabilistic Streams

[BibT_eX]

[DOI]

S. Muthukrishnan

CoRR, 2006

Streaming and sublinear approximation of entropy and information distances.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Approximate quantiles and the order of the stream.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Spatial scan statistics: approximations and performance study.

[BibT_eX]

[DOI]

Deepak Agarwal

Jeff M. Phillips

Zhengyuan Zhu

Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006

2005

Distance distribution of binary codes and the error probability of decoding.

[BibT_eX]

[DOI]

Alexander Barg

IEEE Trans. Inf. Theory, 2005

On graph problems in a semi-streaming model.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Graph distances in the streaming model: the value of space.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

More on reconstructing strings from random traces: insertions and deletions.

[BibT_eX]

[DOI]

Sampath Kannan

Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

Finding Graph Matchings in Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

Approximating the Best-Fit Tree Under L<sub>p</sub> Norms.

[BibT_eX]

[DOI]

Boulos Harb

Sampath Kannan

Proceedings of the Approximation, 2005

2004

Reconstructing strings from random traces.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

List decoding of concatenated codes: improved performance estimates.

[BibT_eX]

[DOI]

Alexander Barg