Andrew McGregor

Hi, I'm an assistant professor in the Department of Computer Science at the University of Massachusetts, Amherst. I'm a member of the theory group and my research is in algorithms and complexity. Specific topics include processing massive data sets and data streams, clustering, approximation algorithms, coding and information theory. Feel free to check out my research papers or cv.

Prior to UMass, I spent a great couple of years at Microsoft Research (Silicon Valley) and the Information Theory and Applications Center at UCSD. In 2007, I received my Ph.D. from the University of Pennsylvania. During graduate school, I spent a summer at DIMACS and three summers at the Fundamental Maths Department at Bell Labs. In the dim and distant past, I received the Certificate of Advanced Study in Mathematics (2001) and a B.A. in Mathematics (2000) from the University of Cambridge.

Here's the text of a short bio and a photo.

---

Since you're here, maybe you'd like to...

• get in contact:
  • Mail: Department of Computer Science, 140 Governor's Drive, University of Massachusetts, Amherst, MA 01003-9264
  • Office: Room 334, 140 Governor's Drive (Campus Map and Area Map)
  • Email: mcgregor at cs.umass.edu
• read some of my favourite papers (see here for more):
  • Analyzing Graph Structure via Linear Measurements and Graph Sketches: Sparsification, Spanners, and Subgraphs
    SODA 2012 and PODS 2012 (with K. Ahn and S. Guha). [Slides], [Video], [Poster].
    And here's a survey about graph stream algorithms that I recently put together.
  • Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
    FOCS 2010 (with A. Chakrabarti, G. Cormode, and R. Kondapally). [Slides].
  • 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). [Slides].
  • Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
    SIAM Journal of Computing, 38 (2009), no. 1, 2044-2059 (with S. Guha)
  • Robust Lower Bounds for Communication and Stream Computation
    STOC 2008 (with A. Chakrabarti and G. Cormode). [Slides].
• submit a great paper to one of the following conferences/workshops that I'm involved with:
  • Towards a Unified Treatment of Dynamic Graphs at Banff International Research Station (2015)
  • Communication Complexity and Applications at Banff International Research Station (2014)
  • ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
  • First International Workshop on Big Dynamic Distributed Data (BD3 2013)
  • String Processing and Information Retrieval Symposium (SPIRE 2013)
  • Workshop on Massive Data Algorithmics (MASSIVE 2013)
  • Data Streams and Compression (Special Session of CiE 2013)
  • 32th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2013)
  • STOC Workshop: Algorithms for Distributed and Streaming Data (STOC 2012)
  • ACM-SIAM Symposium on Theory of Computing Algorithms (STOC 2012)
  • 5th International Frontiers of Algorithmics Workshop (FAW 2011)
  • 19th ACM Conference on Information and Knowledge Management (CIKM 2010)
  • 6th IEEE/ACM International Conference on Distributed Computing in Sensor Systems (DCOSS 2010)
  • ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
  • IIT Kanpur Workshop on Algorithms for Processing Massive Data Sets (2009)
  • DIMACS Workshop on Streaming, Coding, and Compressive Sensing (2009)
• become a Ph.D. student at UMass and work in my group:
  • Great! I like the research I do (admittedly I'm biased) but see my papers to make sure you would too. I'm interested in most areas of theory.
  • A strong math background is a must for any area of theoretical computer science. A good grasp of probability is particularly useful in my work.
  • See here and here for the official application procedure. If you'd like to work with me, mention it in your application and send me an email.
  • For general advice about being a Ph.D. student, check out this, this, and everything here.
  • Unfortunately, I don't have any funds to support summer interns except for students eligible for the REU program.
• review some slides from recent talks on:
  • "Graph Synopses, Sketches, and Streams: A Survey (Part I)" (VLDB Tutorial 2012, Johns Hopkins APL 2011)
  • "Crash Course in Data Streams: Part I" and "Part II" (Johns Hopkins APL 2010).
  • "Data Streams, Dyck Languages, and Detecting Dubious Data Structures" (University of Edinburgh, Random Graals 2010)
  • "Annotations in Data Streams" (INFORMS 2009, IITK WAPMDS 2009)
  • "Graph and Geometry Problems in the Data Stream Model" and "Data Streams: Random Order and Multiple Passes" (Barbados Workshop on Computational Complexity 2009).
  • "Robust Lower Bounds for Communication and Stream Computation" (STOC 2008)
  • "Streaming and Sketching for Distributions" (NIPS 2007)

---

"We know that five minus four is one
But a cloud minus a sailboat
Have no idea what it is."

-- Another Kind of Mathematics, Nichita Stanescu