Publications

 Conference Publications:

 

  • Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
    (with Sepehr Assadi, MohammadHossein Bateni, Vahab Mirrokni,  Cliff Stein)
    In submission to STOC 2018. [arxiv]
  • Distance-preserving graph contractions
    (with Karl Däubel, Yann Disser, Max Klimm, and Freider Smolny)
    Accepted to ITCS 2018. [pdf]
  • Online bipartite matching with amortized O(log^2 n) replacements.
    (with Jacob Holm and Eva Rotenberg)
    Accepted to SODA 2018.   [arxiv]
    Best Paper Award at SODA 2018
  •  Incremental Topological Sort and Cycle Detection in O(m\sqrt{n}) Expected Total Time.
    (with Shiri Chechik).
    Accepted to SODA 2018 [pdf]
  •  Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs.
    In ICALP 2017 [arxiv]
  • General Bounds for Incremental Maximization.
    (with Yann Disser and Martin Gross)
    In ICALP 2017  [arxiv]
  • Simultaneously Load Balancing for Every p-norm, With Reassignments .
    (with Tsvi Kopelowitz, Ely Porat, Seth Pettie, and Clifford Stein)
    In ITCS 2017 [pdf]
  • Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs.
    (with Shiri Chechik)
    In SODA 2017 [pdf]
  • Deterministic decremental single source shortest paths: beyond the o(mn) bound.
    (with Shiri Chechik)
    In STOC 2016 [pdf]
  • Faster Fully Dynamic Matchings with Small Approximation Ratio.
    (with Cliff Stein)
    In SODA 2016 [pdf]
  • Fully Dynamic Matching in Bipartite Graphs.
    (with Cliff Stein)
    In ICALP 2015  [arxiv]
    Best Paper Award at ICALP 2015 (track A).
  • Maintaining shortest paths under deletions in weighted directed graphs.
    In STOC 2013.  Full Version in SICOMP special issue for STOC 2013 [pdf]
    Best Student Paper Award at STOC 2013.
  • Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs.
    In SODA 2012 [pdf]
    Best Student Paper Award at SODA 2012.
  •  Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions.
    (with Liam Roditty)
    In SODA 2011. [pdf]
  • A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs.
    In SODA 2010 [pdf]
    Best Student Paper Award at SODA 2010
  • Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time.
    In FOCS 2009 [pdf]
  •  A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges.
    (with David Karger)
    In STOC 2009 [pdf]
  •   Improved Distance Sensitivity Oracles via Random Sampling.
    (with David Karger)
    In SODA 2008 [pdf]