Email: bernstei at gmail

Positions: I am assistant professor at the department of computer science in Rutgers University (New Brunswick).   Before then I was a PostDoc at TU Berlin, where I was part of the group Combinatorial Algorithms and Graph Optimization (COGA), led by Martin Skutella. I received my Ph.D. from Columbia University (2010-2016), with Cliff Stein as my advisor. I received my undergraduate degree in mathematics from MIT in 2009.

Interests: My research interests are in the design and analysis of 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):

• 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.
• Improved Bounds for Distributed Load Balancing. (With Sepehr Assadi and Zachary Langely). DISC 2020.
  • Best Paper Award at DISC 2020
• 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)
  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