Andrew McGregor

Orcid: 0000-0002-2124-160X

Affiliations:
  • University of Massachusetts Amherst, MA, USA
  • University of Pennsylvania, Philadelphia, PA, USA (PhD 2007)


According to our database1, Andrew McGregor authored at least 117 papers between 2004 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Tight Approximations for Graphical House Allocation.
CoRR, 2023

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

Estimation of Entropy in Constant Space with Improved Sample Complexity.
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.
Proceedings of the 25th International Conference on Database Theory, 2022

Graph Reconstruction from Random Subgraphs.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021
Trace Reconstruction: Generalized and Parameterized.
IEEE Trans. Inf. Theory, 2021

Guest Editorial Special Issue: "From Deletion-Correction to Graph Reconstruction: In Memory of Vladimir I. Levenshtein".
IEEE Trans. Inf. Theory, 2021

PredictRoute: A Network Path Prediction Toolkit.
Proc. ACM Meas. Anal. Comput. Syst., 2021

Correlation Clustering in Data Streams.
Algorithmica, 2021

Cache Me Outside: A New Look at DNS Cache Probing.
Proceedings of the Passive and Active Measurement - 22nd International Conference, 2021

Diverse Data Selection under Fairness Constraints.
Proceedings of the 24th International Conference on Database Theory, 2021

Maximum Coverage in the Data Stream Model: Parameterized and Generalized.
Proceedings of the 24th International Conference on Database Theory, 2021

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs.
Proceedings of the Algorithmic Learning Theory, 2021

Cluster Trellis: Data Structures & Algorithms for Exact Inference in Hierarchical Clustering.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020
Compact Representation of Uncertainty in Hierarchical Clustering.
CoRR, 2020

Vertex Ordering Problems in Directed Graph Streams.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Triangle and Four Cycle Counting in the Data Stream Model.
Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Efficient Intervention Design for Causal Discovery with Latents.
Proceedings of the 37th International Conference on Machine Learning, 2020

Algebraic and Analytic Approaches for Parameter Learning in Mixture Models.
Proceedings of the Algorithmic Learning Theory, 2020

2019
Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate.
IEEE Trans. Inf. Theory, 2019

Better Streaming Algorithms for the Maximum Coverage Problem.
Theory Comput. Syst., 2019

Sample Complexity of Learning Mixtures of Sparse Linear Regressions.
CoRR, 2019

Structural Results on Matching Estimation with Applications to Streaming.
Algorithmica, 2019

The Complexity of Counting Cycles in the Adjacency List Streaming Model.
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Mesh: compacting memory management for C/C++ applications.
Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2019

Sample Complexity of Learning Mixture of Sparse Linear Regressions.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018
Graph Mining on Streams.
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Connect the Dots to Prove It: A Novel Way to Learn Proof Construction.
Proceedings of the 49th ACM Technical Symposium on Computer Science Education, 2018

Compact Representation of Uncertainty in Clustering.
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.
Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Graph Sketching and Streaming: New Approaches for Analyzing Massive Graphs.
Proceedings of the Computer Science - Theory and Applications, 2017

2016
Graph Sketching.
Encyclopedia of Algorithms, 2016

Robust Lower Bounds for Communication and Stream Computation.
Theory Comput., 2016

Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012).
SIAM J. Comput., 2016

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

AutoMan: a platform for integrating human-based and digital computation.
Commun. ACM, 2016

Space-Efficient Estimation of Statistics Over Sub-Sampled Streams.
Algorithmica, 2016

Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Better Algorithms for Counting Triangles in Data Streams.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Stochastic Streams: Sample Complexity vs. Space Complexity.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Planar Matching in Streams Revisited.
Proceedings of the Approximation, 2016

Sketching, Embedding and Dimensionality Reduction in Information Theoretic Spaces.
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 2016

2015
The matrix mechanism: optimizing linear counting queries under differential privacy.
VLDB J., 2015

Kernelization via Sampling with Applications to Dynamic Graph Streams.
CoRR, 2015

Sketching, Embedding, and Dimensionality Reduction for Information Spaces.
CoRR, 2015

Vertex and Hyperedge Connectivity in Dynamic Graph Streams.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Densest Subgraph in Dynamic Graph Streams.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Run Generation Revisited: What Goes Up May or May Not Come Down.
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.
Proceedings of the 2015 IEEE International Conference on Data Mining, 2015

Evaluating Bayesian Networks via Data Streams.
Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014
Annotations in Data Streams.
ACM Trans. Algorithms, 2014

Graph stream algorithms: a survey.
SIGMOD Rec., 2014

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

Verifiable Stream Computation and Arthur-Merlin Communication.
Electron. Colloquium Comput. Complex., 2014

Trace Reconstruction Revisited.
Proceedings of the Algorithms - ESA 2014, 2014

2013
On Interactivity in Arthur-Merlin Communication and Stream Computation.
Electron. Colloquium Comput. Complex., 2013

Homomorphic fingerprints under misalignments: sketching edit and shift distances.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient Nearest-Neighbor Search in the Probability Simplex.
Proceedings of the International Conference on the Theory of Information Retrieval, 2013

Dynamic Graphs in the Sliding-Window Model.
Proceedings of the Algorithms - ESA 2013, 2013

Towards a Theory of Homomorphic Compression.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

Sketching Earth-Mover Distance on Graph Metrics.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Spectral Sparsification in Dynamic Graph Streams.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
CLARO: modeling and processing uncertain data streams.
VLDB J., 2012

SCALLA: A Platform for Scalable One-Pass Analytics Using MapReduce.
ACM Trans. Database Syst., 2012

Graph Synopses, Sketches, and Streams: A Survey.
Proc. VLDB Endow., 2012

The shifting sands algorithm.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Analyzing graph structure via linear measurements.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Graph sketches: sparsification, spanners, and subgraphs.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Approximate Principal Direction Trees.
Proceedings of the 29th International Conference on Machine Learning, 2012

2011
The Limits of Two-Party Differential Privacy.
Electron. Colloquium Comput. Complex., 2011

Polynomial Fitting of Data Streams with Applications to Codeword Testing.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

A platform for scalable one-pass analytics using MapReduce.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2011

Periodicity and Cyclic Shifts via Linear Sketches.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
On the hardness of approximating stopping and trapping sets.
IEEE Trans. Inf. Theory, 2010

A near-optimal algorithm for estimating the entropy of a stream.
ACM Trans. Algorithms, 2010

Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations.
Proc. VLDB Endow., 2010

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.
Electron. Colloquium Comput. Complex., 2010

Optimizing linear counting queries under differential privacy.
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.
Proceedings of the Innovations in Computer Science, 2010

Fast query expansion using approximations of relevance models.
Proceedings of the 19th ACM Conference on Information and Knowledge Management, 2010

2009
Graph Mining on Streams.
Proceedings of the Encyclopedia of Database Systems, 2009

Sublinear estimation of entropy and information distances.
ACM Trans. Algorithms, 2009

Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams.
SIAM J. Comput., 2009

Probabilistic Histograms for Probabilistic Data.
Proc. VLDB Endow., 2009

Optimizing Histogram Queries under Differential Privacy
CoRR, 2009

Estimating the confidence of conditional functional dependencies.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2009

Annotations in Data Streams.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

The Oil Searching Problem.
Proceedings of the Algorithms, 2009

2008
Estimating statistical aggregates on probabilistic data streams.
ACM Trans. Database Syst., 2008

Graph Distances in the Data-Stream Model.
SIAM J. Comput., 2008

Sketching information divergences.
Mach. Learn., 2008

Better Bounds for Frequency Moments in Random-Order Streams
CoRR, 2008

Declaring independence via the sketching of sketches.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Approximation algorithms for clustering uncertain data.
Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

Sorting and Selection with Random Costs.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Finding Metric Structure in Information Theoretic Clustering.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007
Space-Efficient Sampling.
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, 2007

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

Island hopping and path colouring with applications to WDM network design.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

A near-optimal algorithm for computing the entropy of a stream.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Checking and Spot-Checking the Correctness of Priority Queues.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
Estimating Aggregate Properties on Probabilistic Streams
CoRR, 2006

Streaming and sublinear approximation of entropy and information distances.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Approximate quantiles and the order of the stream.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Spatial scan statistics: approximations and performance study.
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.
IEEE Trans. Inf. Theory, 2005

On graph problems in a semi-streaming model.
Theor. Comput. Sci., 2005

Graph distances in the streaming model: the value of space.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

More on reconstructing strings from random traces: insertions and deletions.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

Finding Graph Matchings in Data Streams.
Proceedings of the Approximation, 2005

Approximating the Best-Fit Tree Under L<sub>p</sub> Norms.
Proceedings of the Approximation, 2005

2004
Reconstructing strings from random traces.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

List decoding of concatenated codes: improved performance estimates.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004


  Loading...