Andrew McGregor

165 papers A* 39A 21B 9C 1Misc 4Journal 74Unranked 14
YearRankTypeTitle / Venue / Authors
2024 B conf
Graph Reconstruction from Noisy Random Subgraphs.
ISIT
Andrew McGregor, Rik Sengupta
2024 J jnl
Graph Reconstruction from Noisy Random Subgraphs.
CoRR
Andrew McGregor, Rik Sengupta
2024 J jnl
Graphical house allocation with identical valuations.
Auton. Agents Multi Agent Syst.
Hadi Hosseini, Andrew McGregor, Justin Payan, Rik Sengupta, Rohit Vaish, Vignesh Viswanathan
2024 A conf
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams.
ESA
Amit Chakrabarti, Andrew McGregor, Anthony Wirth
2024 J jnl
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams.
CoRR
Amit Chakrabarti, Andrew McGregor, Anthony Wirth
2024 — conf
Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model.
FSTTCS
Christian Konrad, Andrew McGregor, Rik Sengupta, Cuong Than
2024 Misc conf
Scalable Scheduling Policies for Quantum Satellite Networks.
QCE
Albert Williams, Nitish K. Panigrahy, Andrew McGregor, Don Towsley
2024 J jnl
Scalable Scheduling Policies for Quantum Satellite Networks.
CoRR
Albert Williams, Nitish K. Panigrahy, Andrew McGregor, Don Towsley
2024 A conf
Tight Approximations for Graphical House Allocation.
AAMAS
Hadi Hosseini, Andrew McGregor, Rik Sengupta, Rohit Vaish, Vignesh Viswanathan
2023 J jnl
Tight Approximations for Graphical House Allocation.
CoRR
Hadi Hosseini, Andrew McGregor, Rik Sengupta, Rohit Vaish, Vignesh Viswanathan
2022 A* conf
Estimation of Entropy in Constant Space with Improved Sample Complexity.
NeurIPS
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
2022 J jnl
Estimation of Entropy in Constant Space with Improved Sample Complexity.
CoRR
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
2022 A* conf
Graph Reconstruction from Random Subgraphs.
ICALP
Andrew McGregor, Rik Sengupta
2022 A conf
Improved Approximation and Scalability for Fair Max-Min Diversification.
ICDT
Raghavendra Addanki, Andrew McGregor, Alexandra Meliou, Zafeiria Moumoulidou
2022 J jnl
Improved Approximation and Scalability for Fair Max-Min Diversification.
CoRR
Raghavendra Addanki, Andrew McGregor, Alexandra Meliou, Zafeiria Moumoulidou
2022 J jnl
Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests.
CoRR
Erica Cai, Andrew McGregor, David D. Jensen
2022 A conf
Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries.
ESA
Raghavendra Addanki, Andrew McGregor, Cameron Musco
2022 J jnl
Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries.
CoRR
Raghavendra Addanki, Andrew McGregor, Cameron Musco
2021 B conf
Cache Me Outside: A New Look at DNS Cache Probing.
PAM
Arian Akhavan Niaki, William R. Marczak, Sahand Farhoodi, Andrew McGregor, Phillipa Gill, Nicholas Weaver
2021 A conf
Cluster Trellis: Data Structures & Algorithms for Exact Inference in Hierarchical Clustering.
AISTATS
Sebastian Macaluso, Craig S. Greenberg, Nicholas Monath, Ji Ah Lee, Patrick Flaherty, Kyle Cranmer, Andrew McGregor, Andrew McCallum
2021 J jnl
Correlation Clustering in Data Streams.
Algorithmica
Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, Anthony Wirth
2021 A conf
Diverse Data Selection under Fairness Constraints.
ICDT
Zafeiria Moumoulidou, Andrew McGregor, Alexandra Meliou
2021 J jnl
Guest Editorial Special Issue: "From Deletion-Correction to Graph Reconstruction: In Memory of Vladimir I. Levenshtein".
IEEE Trans. Inf. Theory
Alexander Barg, Lara Dolecek, Ryan Gabrys, Gyula O. H. Katona, János Körner, Andrew McGregor, Olgica Milenkovic, Sihem Mesnager, Gilles Zémor
2021 B conf
Intervention Efficient Algorithms for Approximate Learning of Causal Graphs.
ALT
Raghavendra Addanki, Andrew McGregor, Cameron Musco
2021 A conf
Maximum Coverage in the Data Stream Model: Parameterized and Generalized.
ICDT
Andrew McGregor, David Tench, Hoa T. Vu
2021 J jnl
Maximum Coverage in the Data Stream Model: Parameterized and Generalized.
CoRR
Andrew McGregor, David Tench, Hoa T. Vu
2021 — conf
PredictRoute: A Network Path Prediction Toolkit.
SIGMETRICS (Abstracts)
Rachee Singh, David Tench, Phillipa Gill, Andrew McGregor
2021 J jnl
PredictRoute: A Network Path Prediction Toolkit.
Proc. ACM Meas. Anal. Comput. Syst.
Rachee Singh, David Tench, Phillipa Gill, Andrew McGregor
2021 J jnl
Trace Reconstruction: Generalized and Parameterized.
IEEE Trans. Inf. Theory
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
2021 J jnl
Vertex Ordering Problems in Directed Graph Streams.
CoRR
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
2020 B conf
Algebraic and Analytic Approaches for Parameter Learning in Mixture Models.
ALT
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
2020 J jnl
Algebraic and Analytic Approaches for Parameter Learning in Mixture Models.
CoRR
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
2020 J jnl
Compact Representation of Uncertainty in Hierarchical Clustering.
CoRR
Craig S. Greenberg, Sebastian Macaluso, Nicholas Monath, Ji Ah Lee, Patrick Flaherty, Kyle Cranmer, Andrew McGregor, Andrew McCallum
2020 J jnl
Diverse Data Selection under Fairness Constraints.
CoRR
Zafeiria Moumoulidou, Andrew McGregor, Alexandra Meliou
2020 A* conf
Efficient Intervention Design for Causal Discovery with Latents.
ICML
Raghavendra Addanki, Shiva Prasad Kasiviswanathan, Andrew McGregor, Cameron Musco
2020 J jnl
Efficient Intervention Design for Causal Discovery with Latents.
CoRR
Raghavendra Addanki, Shiva Prasad Kasiviswanathan, Andrew McGregor, Cameron Musco
2020 J jnl
Intervention Efficient Algorithms for Approximate Learning of Causal Graphs.
CoRR
Raghavendra Addanki, Andrew McGregor, Cameron Musco
2020 A* conf
Triangle and Four Cycle Counting in the Data Stream Model.
PODS
Andrew McGregor, Sofya Vorotnikova
2020 A* conf
Vertex Ordering Problems in Directed Graph Streams.
SODA
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
2019 J jnl
Better Streaming Algorithms for the Maximum Coverage Problem.
Theory Comput. Syst.
Andrew McGregor, Hoa T. Vu
2019 J jnl
Mesh: Compacting Memory Management for C/C++ Applications.
CoRR
Bobby Powers, David Tench, Emery D. Berger, Andrew McGregor
2019 A* conf
Mesh: compacting memory management for C/C++ applications.
PLDI
Bobby Powers, David Tench, Emery D. Berger, Andrew McGregor
2019 A* conf
Sample Complexity of Learning Mixture of Sparse Linear Regressions.
NeurIPS
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
2019 J jnl
Sample Complexity of Learning Mixtures of Sparse Linear Regressions.
CoRR
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
2019 J jnl
Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate.
IEEE Trans. Inf. Theory
Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova
2019 J jnl
Structural Results on Matching Estimation with Applications to Streaming.
Algorithmica
Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, Samson Zhou
2019 A* conf
The Complexity of Counting Cycles in the Adjacency List Streaming Model.
PODS
John Kallaugher, Andrew McGregor, Eric Price, Sofya Vorotnikova
2019 A conf
Trace Reconstruction: Generalized and Parameterized.
ESA
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
2019 J jnl
Trace Reconstruction: Generalized and Parameterized.
CoRR
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
2019 J jnl
Verifiable Stream Computation and Arthur-Merlin Communication.
SIAM J. Comput.
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
2018 — conf
A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs.
SOSA
Andrew McGregor, Sofya Vorotnikova
2018 A* conf
Compact Representation of Uncertainty in Clustering.
NeurIPS
Craig S. Greenberg, Nicholas Monath, Ari Kobren, Patrick Flaherty, Andrew McGregor, Andrew McCallum
2018 A conf
Connect the Dots to Prove It: A Novel Way to Learn Proof Construction.
SIGCSE
Mark McCartin-Lim, Beverly P. Woolf, Andrew McGregor
2018 J jnl
Correlation Clustering in Data Streams.
CoRR
Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, Anthony Wirth
2018 — ch.
Graph Mining on Streams.
Encyclopedia of Database Systems (2nd ed.)
Andrew McGregor
2017 A conf
Better Streaming Algorithms for the Maximum Coverage Problem.
ICDT
Andrew McGregor, Hoa T. Vu
2017 Misc conf
Graph Sketching and Streaming: New Approaches for Analyzing Massive Graphs.
CSR
Andrew McGregor
2017 J jnl
Storage Capacity as an Information-Theoretic Analogue of Vertex Cover.
CoRR
Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova
2017 B conf
Storage capacity as an information-theoretic analogue of vertex cover.
ISIT
Arya Mazumdar, Andrew McGregor, Sofya Vorotnikova
2016 J jnl
A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs.
CoRR
Andrew McGregor, Sofya Vorotnikova
2016 J jnl
AutoMan: a platform for integrating human-based and digital computation.
Commun. ACM
Daniel W. Barowy, Charlie Curtsinger, Emery D. Berger, Andrew McGregor
2016 A* conf
Better Algorithms for Counting Triangles in Data Streams.
PODS
Andrew McGregor, Sofya Vorotnikova, Hoa T. Vu
2016 J jnl
Better Streaming Algorithms for the Maximum Coverage Problem.
CoRR
Andrew McGregor, Hoa T. Vu
2016 — ch.
Graph Sketching.
Encyclopedia of Algorithms
Andrew McGregor
2016 A* conf
Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.
SODA
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova
2016 — conf
Planar Matching in Streams Revisited.
APPROX-RANDOM
Andrew McGregor, Sofya Vorotnikova
2016 J jnl
Robust Lower Bounds for Communication and Stream Computation.
Theory Comput.
Amit Chakrabarti, Graham Cormode, Andrew McGregor
2016 A conf
Sketching, Embedding and Dimensionality Reduction in Information Theoretic Spaces.
AISTATS
Amirali Abdullah, Ravi Kumar, Andrew McGregor, Sergei Vassilvitskii, Suresh Venkatasubramanian
2016 J jnl
Space-Efficient Estimation of Statistics Over Sub-Sampled Streams.
Algorithmica
Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff
2016 J jnl
Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012).
SIAM J. Comput.
Andrew McGregor, Rahul Santhanam
2016 A conf
Stochastic Streams: Sample Complexity vs. Space Complexity.
ESA
Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff
2015 A* conf
Catching the Head, Tail, and Everything in Between: A Streaming Algorithm for the Degree Distribution.
ICDM
Olivia Simpson, C. Seshadhri, Andrew McGregor
2015 J jnl
Catching the head, the tail, and everything in between: a streaming algorithm for the degree distribution.
CoRR
Olivia Simpson, C. Seshadhri, Andrew McGregor
2015 A* conf
Correlation Clustering in Data Streams.
ICML
Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, Anthony Wirth
2015 — conf
Densest Subgraph in Dynamic Graph Streams.
MFCS (2)
Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu
2015 J jnl
Densest Subgraph in Dynamic Graph Streams.
CoRR
Andrew McGregor, David Tench, Sofya Vorotnikova, Hoa T. Vu
2015 Misc conf
Evaluating Bayesian Networks via Data Streams.
COCOON
Andrew McGregor, Hoa T. Vu
2015 J jnl
Kernelization via Sampling with Applications to Dynamic Graph Streams.
CoRR
Rajesh Hemant Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova
2015 B conf
Run Generation Revisited: What Goes Up May or May Not Come Down.
ISAAC
Michael A. Bender, Samuel McCauley, Andrew McGregor, Shikha Singh, Hoa T. Vu
2015 J jnl
Run Generation Revisited: What Goes Up May or May Not Come Down.
CoRR
Michael A. Bender, Samuel McCauley, Andrew McGregor, Shikha Singh, Hoa T. Vu
2015 J jnl
Sketching, Embedding, and Dimensionality Reduction for Information Spaces.
CoRR
Amirali Abdullah, Ravi Kumar, Andrew McGregor, Sergei Vassilvitskii, Suresh Venkatasubramanian
2015 J jnl
The matrix mechanism: optimizing linear counting queries under differential privacy.
VLDB J.
Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, Vibhor Rastogi
2015 A conf
Verifiable Stream Computation and Arthur-Merlin Communication.
CCC
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
2015 A* conf
Vertex and Hyperedge Connectivity in Dynamic Graph Streams.
PODS
Sudipto Guha, Andrew McGregor, David Tench
2014 J jnl
Algorithms for Large Scale Graphs (NII Shonan Meeting 2014-12).
NII Shonan Meet. Rep.
Andrew McGregor, Gopal Pandurangan, Sergei Vassilvitskii
2014 J jnl
Annotations in Data Streams.
ACM Trans. Algorithms
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler
2014 J jnl
Graph stream algorithms: a survey.
SIGMOD Rec.
Andrew McGregor
2014 A conf
Trace Reconstruction Revisited.
ESA
Andrew McGregor, Eric Price, Sofya Vorotnikova
2014 J jnl
Verifiable Stream Computation and Arthur-Merlin Communication.
Electron. Colloquium Comput. Complex.
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
2013 A conf
Dynamic Graphs in the Sliding-Window Model.
ESA
Michael S. Crouch, Andrew McGregor, Daniel M. Stubbs
2013 Misc conf
Efficient Nearest-Neighbor Search in the Probability Simplex.
ICTIR
Kriste Krstovski, David A. Smith, Hanna M. Wallach, Andrew McGregor
2013 A* conf
Homomorphic fingerprints under misalignments: sketching edit and shift distances.
STOC
Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat
2013 J jnl
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.
SIAM J. Comput.
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
2013 J jnl
On Interactivity in Arthur-Merlin Communication and Stream Computation.
Electron. Colloquium Comput. Complex.
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian
2013 — conf
Sketching Earth-Mover Distance on Graph Metrics.
APPROX-RANDOM
Andrew McGregor, Daniel M. Stubbs
2013 — conf
Spectral Sparsification in Dynamic Graph Streams.
APPROX-RANDOM
Kook Jin Ahn, Sudipto Guha, Andrew McGregor
2013 C conf
Towards a Theory of Homomorphic Compression.
CiE
Andrew McGregor
2012 A* conf
Analyzing graph structure via linear measurements.
SODA
Kook Jin Ahn, Sudipto Guha, Andrew McGregor
2012 J jnl
Annotations in Data Streams.
Electron. Colloquium Comput. Complex.
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler
2012 J jnl
Approximate Principal Direction Trees
CoRR
Mark McCartin-Lim, Andrew McGregor, Rui Wang
2012 A* conf
Approximate Principal Direction Trees.
ICML
Mark McCartin-Lim, Andrew McGregor, Rui Wang
2012 A conf
AutoMan: a platform for integrating human-based and digital computation.
OOPSLA
Daniel W. Barowy, Charlie Curtsinger, Emery D. Berger, Andrew McGregor
2012 J jnl
CLARO: modeling and processing uncertain data streams.
VLDB J.
Thanh T. L. Tran, Liping Peng, Yanlei Diao, Andrew McGregor, Anna Liu
2012 J jnl
Graph Synopses, Sketches, and Streams: A Survey.
Proc. VLDB Endow.
Sudipto Guha, Andrew McGregor
2012 A* conf
Graph sketches: sparsification, spanners, and subgraphs.
PODS
Kook Jin Ahn, Sudipto Guha, Andrew McGregor
2012 J jnl
SCALLA: A Platform for Scalable One-Pass Analytics Using MapReduce.
ACM Trans. Database Syst.
Boduo Li, Edward Mazur, Yanlei Diao, Andrew McGregor, Prashant J. Shenoy
2012 A* conf
Space-efficient estimation of statistics over sub-sampled streams.
PODS
Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff
2012 A* conf
The shifting sands algorithm.
SODA
Andrew McGregor, Paul Valiant
2011 — conf
A platform for scalable one-pass analytics using MapReduce.
SIGMOD Conference
Boduo Li, Edward Mazur, Yanlei Diao, Andrew McGregor, Prashant J. Shenoy
2011 — conf
Periodicity and Cyclic Shifts via Linear Sketches.
APPROX-RANDOM
Michael S. Crouch, Andrew McGregor
2011 A conf
Polynomial Fitting of Data Streams with Applications to Codeword Testing.
STACS
Andrew McGregor, Atri Rudra, Steve Uurtamo
2011 J jnl
Robust Lower Bounds for Communication and Stream Computation.
Electron. Colloquium Comput. Complex.
Amit Chakrabarti, Graham Cormode, Andrew McGregor
2011 J jnl
The Limits of Two-Party Differential Privacy.
Electron. Colloquium Comput. Complex.
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan
2010 J jnl
A near-optimal algorithm for estimating the entropy of a stream.
ACM Trans. Algorithms
Amit Chakrabarti, Graham Cormode, Andrew McGregor
2010 J jnl
Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations.
Proc. VLDB Endow.
Thanh T. L. Tran, Andrew McGregor, Yanlei Diao, Liping Peng, Anna Liu
2010 A conf
Fast query expansion using approximations of relevance models.
CIKM
Marc-Allen Cartright, James Allan, Victor Lavrenko, Andrew McGregor
2010 J jnl
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
CoRR
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
2010 A* conf
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.
FOCS
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
2010 J jnl
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition.
Electron. Colloquium Comput. Complex.
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor
2010 J jnl
On the hardness of approximating stopping and trapping sets.
IEEE Trans. Inf. Theory
Andrew McGregor, Olgica Milenkovic
2010 A* conf
Optimizing linear counting queries under differential privacy.
PODS
Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, Andrew McGregor
2010 A conf
Space-Efficient Estimation of Robust Statistics and Distribution Testing.
ICS
Steve Chien, Katrina Ligett, Andrew McGregor
2010 A* conf
The Limits of Two-Party Differential Privacy.
FOCS
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan
2009 — conf
Annotations in Data Streams.
ICALP (1)
Amit Chakrabarti, Graham Cormode, Andrew McGregor
2009 — conf
Estimating the confidence of conditional functional dependencies.
SIGMOD Conference
Graham Cormode, Lukasz Golab, Flip Korn, Andrew McGregor, Divesh Srivastava, Xi Zhang
2009 — ch.
Graph Mining on Streams.
Encyclopedia of Database Systems
Andrew McGregor
2009 J jnl
Optimizing Histogram Queries under Differential Privacy
CoRR
Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, Andrew McGregor
2009 J jnl
Probabilistic Histograms for Probabilistic Data.
Proc. VLDB Endow.
Graham Cormode, Antonios Deligiannakis, Minos N. Garofalakis, Andrew McGregor
2009 J jnl
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams.
SIAM J. Comput.
Sudipto Guha, Andrew McGregor
2009 J jnl
Sublinear estimation of entropy and information distances.
ACM Trans. Algorithms
Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian
2009 A conf
The Oil Searching Problem.
ESA
Andrew McGregor, Krzysztof Onak, Rina Panigrahy
2008 A* conf
Approximation algorithms for clustering uncertain data.
PODS
Graham Cormode, Andrew McGregor
2008 J jnl
Better Bounds for Frequency Moments in Random-Order Streams
CoRR
Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy
2008 A* conf
Declaring independence via the sketching of sketches.
SODA
Piotr Indyk, Andrew McGregor
2008 J jnl
Estimating statistical aggregates on probabilistic data streams.
ACM Trans. Database Syst.
T. S. Jayram, Andrew McGregor, S. Muthukrishnan, Erik Vee
2008 A* conf
Finding Metric Structure in Information Theoretic Clustering.
COLT
Kamalika Chaudhuri, Andrew McGregor
2008 J jnl
Graph Distances in the Data-Stream Model.
SIAM J. Comput.
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang
2008 A* conf
Robust lower bounds for communication and stream computation.
STOC
Amit Chakrabarti, Graham Cormode, Andrew McGregor
2008 J jnl
Sketching information divergences.
Mach. Learn.
Sudipto Guha, Piotr Indyk, Andrew McGregor
2008 B conf
Sorting and Selection with Random Costs.
LATIN
Stanislav Angelov, Keshav Kunal, Andrew McGregor
2008 — conf
Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination.
ICALP (1)
Sudipto Guha, Andrew McGregor
2007 A* conf
A near-optimal algorithm for computing the entropy of a stream.
SODA
Amit Chakrabarti, Graham Cormode, Andrew McGregor
2007 A* conf
Checking and Spot-Checking the Correctness of Priority Queues.
ICALP
Matthew Chu, Sampath Kannan, Andrew McGregor
2007 A* conf
Estimating statistical aggregates on probabilistic data streams.
PODS
T. S. Jayram, Andrew McGregor, S. Muthukrishnan, Erik Vee
2007 A* conf
Island hopping and path colouring with applications to WDM network design.
SODA
Andrew McGregor, F. Bruce Shepherd
2007 A* conf
Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming.
ICALP
Sudipto Guha, Andrew McGregor
2007 J jnl
On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
CoRR
Andrew McGregor, Olgica Milenkovic
2007 A* conf
Sketching Information Divergences.
COLT
Sudipto Guha, Piotr Indyk, Andrew McGregor
2007 J jnl
Sorting and Selection with Random Costs
CoRR
Stanislav Angelov, Keshav Kunal, Andrew McGregor
2007 A conf
Space-Efficient Sampling.
AISTATS
Sudipto Guha, Andrew McGregor
2006 A* conf
Approximate quantiles and the order of the stream.
PODS
Sudipto Guha, Andrew McGregor
2006 J jnl
Estimating Aggregate Properties on Probabilistic Streams
CoRR
Andrew McGregor, S. Muthukrishnan
2006 A* conf
Spatial scan statistics: approximations and performance study.
KDD
Deepak Agarwal, Andrew McGregor, Jeff M. Phillips, Suresh Venkatasubramanian, Zhengyuan Zhu
2006 A* conf
Streaming and sublinear approximation of entropy and information distances.
SODA
Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian
2005 — conf
Approximating the Best-Fit Tree Under L
APPROX-RANDOM
Boulos Harb, Sampath Kannan, Andrew McGregor
2005 J jnl
Distance distribution of binary codes and the error probability of decoding.
IEEE Trans. Inf. Theory
Alexander Barg, Andrew McGregor
2005 — conf
Finding Graph Matchings in Data Streams.
APPROX-RANDOM
Andrew McGregor
2005 A* conf
Graph distances in the streaming model: the value of space.
SODA
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang
2005 B conf
More on reconstructing strings from random traces: insertions and deletions.
ISIT
Sampath Kannan, Andrew McGregor
2005 J jnl
On graph problems in a semi-streaming model.
Theor. Comput. Sci.
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang
2005 J jnl
Streaming and Sublinear Approximation of Entropy and Information Distances
CoRR
Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian
2004 J jnl
Distance distribution of binary codes and the error probability of decoding
CoRR
Alexander Barg, Andrew McGregor
2004 B conf
List decoding of concatenated codes: improved performance estimates.
ISIT
Alexander Barg, Andrew McGregor
2004 A* conf
On Graph Problems in a Semi-streaming Model.
ICALP
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang
2004 A* conf
Reconstructing strings from random traces.
SODA
Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor