Email: bernstei at gmail

Positions:  I have moved to NYU! See below for my new website. 

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. 

https://wp.nyu.edu/tandonschoolofengineering-aaronbernstein/

 

Prospective PhD Students: I am hiring a PhD student to start in Fall 2025. I am looking for students who have a strong background specifically in math or theoretical computer science. For more information, see my NYU website.

Interests: My research interests are in the design and analysis of algorithms, especially graph algorithms. Specific topics include sublinear algorithms for processing large inputs (e.g. streaming, parallel), dynamic graph algorithms, online algorithms, distributed algorithms, fault-tolerant algorithms, and approximation algorithms.

Selected Conference Publications: (see publications tab for the full list):

 

  • Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time. (With  Joakim Blikstad, Thatchaphol Saranurak, and Ta-Wei Tu). FOCS 2024. [arxiv]
  • 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]
  • Improved Bounds for Distributed Load Balancing. (With Sepehr Assadi and Zachary Langely). DISC 2020. [arxiv]
    Best Paper Award at DISC 2020
  • Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. (With Maximillian Probst Gutenberg and Thatchaphol Saranurak). FOCS 2020. [arxiv]
  • Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time. (With Christian Wulff-Nilsen and Maximilian Probst). STOC 2019.  [arxiv]
    Invited to SICOMP special issue for STOC 2019
  • Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time. (With Danupon Nanongkai).STOC 2019. [arxiv]
    Invited to SICOMP special issue for STOC 2019
  • Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. (With Sepehr Assadi, MohammadHossein Bateni, Vahab Mirrokni,  Cliff Stein). SODA 2019  [arxiv]
  • Online bipartite matching with amortized O(log^2 n) replacements. (With Jacob Holm and Eva Rotenberg)
    Accepted to Symposium on Discrete Algorithms (SODA) 2018.  [arxiv]
    Best Paper Award at SODA 2018 
  • Deterministic decremental single source shortest paths: beyond the o(mn) bound. (With Shiri Chechik)
    Symposium on Theorem of Computing (STOC) 2016. [pdf]
  • Fully Dynamic Matching in Bipartite Graphs. (With Cliff Stein)
    International Colloquium on Automata, Languages, and Programming  (ICALP) 2015.
    Best Paper Award at ICALP 2015 (track A) [arxiv]
  • Maintaining shortest paths under deletions in weighted directed graphs.
    Symposium on Theorem of Computing (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.
    Symposium on Discrete Algorithms (SODA) 2012. [pdf]
    Best Student Paper Award at SODA 2012
  • A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs.
    Symposium on Discrete Algorithms (SODA) 2010. [pdf]
    Best Student Paper Award at SODA 2010