Conference Publications:
- 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.
- Improved Bounds for Distributed Load Balancing. (With Sepehr Assadi and Zachary Langely). DISC 2020.
- Best Paper Award at DISC 2020
- Online Matching with Recourse: Random Edge Arrivals. (With Aditi Dudeja.) FSTTCS 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. [arxiv] - Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time. (With Danupon Nanongkai).STOC 2019. [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)
Accepted to SODA 2018. [arxiv]
Best Paper Award at SODA 2018
- Incremental Topological Sort and Cycle Detection in O(msqrt{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]