aaronbernstein.cs.rutgers.edu Open in urlscan Pro
128.6.48.118  Public Scan

Form analysis
1 forms found in the DOM

GET https://aaronbernstein.cs.rutgers.edu/

<form role="search" method="get" class="search-form" action="https://aaronbernstein.cs.rutgers.edu/">
  <label>
    <span class="screen-reader-text">Search for:</span>
    <input type="search" class="search-field" placeholder="Search …" value="" name="s">
  </label>
  <input type="submit" class="search-submit" value="Search">
</form>

Text Content

Skip to content


AARON BERNSTEIN

Menu
 * Home
 * Publications


 

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

Search for:
Copyright ©2018, Rutgers, The State University of New Jersey, an equal
opportunity, affirmative action institution. All rights reserved.