Research Interests

Streaming algorithms, dynamic algorithms, distributed algorithms, graph algorithms, graph theory, communication complexity, information theory.

Journal Publications

  1. Storage Capacity as an Information-Theoretic Vertex Cover and the Index Coding Rate
    A. Mazumdar, A. McGregor, S. Vorotnikova
    IEEE Transactions on Information Theory 2019

  2. Structural Results on Matching Estimation with Applications to Streaming [PDF]
    M. Bury, E. Grigorescu, A. McGregor, M. Monemizadeh, C. Schwiegelshohn, S. Vorotnikova, S. Zhou
    Algorithmica 2018

Conference Publications

  1. The Complexity of Counting Cycles in the Adjacency List Streaming Model
    J. Kallaugher, A. McGregor, E. Price, S. Vorotnikova
    PODS 2019

  2. A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs [PDF] [Slides]
    A. McGregor, S. Vorotnikova
    SOSA 2018

  3. Storage Capacity as an Information-Theoretic Analogue of Vertex Cover [PDF] [Slides]
    A. Mazumdar, A. McGregor, S. Vorotnikova
    ISIT 2017

  4. Planar Matchings in Streams Revisited [PDF] [Slides]
    A. McGregor, S. Vorotnikova
    APPROX 2016

  5. Better Algorithms for Counting Triangles in Data Streams [PDF]
    A. McGregor, S. Vorotnikova, H. Vu
    PODS 2016

  6. Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams [PDF] [Slides] [Poster]
    R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, A. McGregor, M. Monemizadeh, S. Vorotnikova
    SODA 2016

  7. Densest Subgraph in Dynamic Graph Streams [PDF]
    A. McGregor, D. Tench, S. Vorotnikova, H. Vu
    MFCS 2015

  8. Trace Reconstruction Revisited [PDF] [Slides]
    A. McGregor, E. Price, S. Vorotnikova
    ESA 2014

Talks and Poster Sessions

  1. Streaming Algorithms for Matchings in Low Arboricity Graphs
    Workshop on Data Summarisation, University of Warwick, UK, 2018 [Slides]
    Simons Institute for the Theory of Computing, Berkeley, CA, 2018 [Slides]

  2. A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs [Slides]
    SOSA, New Orleans LA, 2018

  3. Storage Capacity as an Information-Theoretic Analogue of Vertex Cover [Slides]
    ISIT, Aachen, Germany, 2017

  4. Solving Graph Problems in the Streaming Model [Slides]
    Invited talk for CSWomen group at UMass Amherst, 2016

  5. Planar Matchings in Streams Revisited [Slides]
    APPROX+RANDOM, Paris, France, 2016

  6. Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams [Slides]
    SODA, Arlington VA, 2016

  7. Parameterized Vertex Cover, Hitting Set, and Matching in Dynamic Graphs [Poster]
    Big Data and Sublinear Algorithms Workshop, Rutgers University, DIMACS, 2015
    CRA-Women Grad Cohort Workshop, San Francisco, 2015

  8. Trace Reconstruction Revisited [Slides]
    ESA, Poland, 2014

  9. Variations of Cops and Robber on Graphs [Slides]
    JMM, Special Session on Research in Mathematics by Undergraduates, San Diego, 2013
    SUMMR, Michigan State University, 2012