Research Interests

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

Publications

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

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

  3. Storage Capacity as an Information-Theoretic Analogue of Vertex Cover [PDF] [Slides]
    ISIT 2017 (with A. Mazumdar and A. McGregor)

  4. Planar Matchings in Streams Revisited [PDF] [Slides]
    APPROX 2016 (with A. McGregor)

  5. Better Algorithms for Counting Triangles in Data Streams [PDF]
    PODS 2016 (with A. McGregor and H. Vu)

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

  7. Densest Subgraph in Dynamic Graph Streams [PDF]
    MFCS 2015 (with A. McGregor, D. Tench, and H. Vu)

  8. Trace Reconstruction Revisited [PDF] [Slides]
    ESA 2014 (with A. McGregor and E. Price)

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