Conference Publications:

  • Closing the Gap Between Directed Hopsets and Shortcut Sets. (With Nicole Wein). SODA 2023. [arxiv]
  • Negative-Weight Single-Source Shortest Paths in Near-Linear Time. (With Danupon Nanongkai and Christian Wulff-Nilsen.) FOCS 2022. [arxiv]
    Best Paper Award at FOCS 2022
  • Decremental Matching in General Graphs. (With Sepehr Assadi and Aditi Dudeja). ICALP 2022. [arxiv]
  • Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. (With Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun). ICALP 2022. [arxiv]
  • Incremental SCC maintenance in sparse graphs. (With Aditi Dudeja and Seth Pettie). ESA 2021. [website] 
  • Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. (With Maximillian Probst Gutenberg and Thatchaphol Saranurak). FOCS 2021. arxiv
  • A Framework for Dynamic Matching in Weighted Graphs. (With Aditi Dudeja and Zach Langely.) STOC 2021. [pdf]
  • Near-Optimal Decremental SSSP in Dense Weighted Digraphs. (With Maximillian Probst Gutenberg and Christian Wulff-Nilsen). FOCS 2020. [arxiv]
  • Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. (With Maximillian Probst Gutenberg and Thatchaphol Saranurak). FOCS 2020. [arxiv]
  • Online Matching with Recourse: Random Edge Arrivals. (With Aditi Dudeja). FSTTCS 2020. [website]
  • Improved Bounds for Distributed Load Balancing. (With Sepehr Assadi and Zachary Langely). DISC 2020. [arxiv]
    Best Paper award at DISC 2020. 
  • Improved Bounds for Matching in Random Order Streams. ICALP 2020. Invited to Special Issue of Theory of Computing Systems. [arxiv]
  • Decremental Strongly-Connected Components and
    Single-Source Reachability in Near-Linear Time.     (With Christian Wulff-Nilsen and Maximilian Probst). STOC 2019. Invited to Sicomp Special Issue.      [arxiv]
  • Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time. (With Danupon Nanongkai). STOC 2019. Invited to Sicomp Special Issue. [arxiv]
  • Towards a Unified Theory of Sparsification for Matching Problems. (With Sepehr Assadi). SOSA 2019. [arxiv]
  • A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.  (With Monika Henzinger and Sebastian Forster). SODA 2019. [arxiv]
  • Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. (With Sepehr Assadi, MohammadHossein Bateni, Vahab Mirrokni,  Cliff Stein). SODA 2019  [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). 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). 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]