Email: aaron.bernstein@nyu.edu
Position: Charles S. Baylis Associate Professor of Computer Science at NYU Tandon. Previously I was a professor at Rutgers from Fall 2018 – Spring 2024. I received my Ph.D. from Columbia University (2010–2016), with Cliff Stein as my advisor.
Interests: Design and analysis of algorithms, especially graph algorithms. Specific topics include sublinear algorithms (e.g. streaming/parallel), dynamic graph algorithms, online algorithms, distributed algorithms, and approximation algorithms.
NYU Theory: I am part of the theory group at NYU, which spans both CS@Tandon and CS@Courant.
Prospective PhD Students: I am hiring a PhD student for Fall 2025. I am specifically looking for students with a strong background in math or theoretical computer science. If you are interested in working with me, make sure to apply to NYU Tandon. The theory group is joint between NYU Courant and NYU Tandon, so students can work with and take classes with professors from both departments. But I will only see your application if you apply to Tandon. See more details here.
Advising:
— Vikrant Ashvinkumar (at Rutgers, co-advised with Jie Gao, 2020–now)
— Zach Langely (2019–2024).
— Aditi Dudeja (2017–2023).
Selected Publications:
- Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time. (With Joakim Blikstad, Thatchaphol Saranurak, and Ta-Wei Tu). FOCS 2024. [arxiv]
Invited to Sicomp Special Issue. - 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 - 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]
- 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] - 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. - 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]