I am applying for academic job positions to start in Fall 2018.  All my application materials can be found in the job materials tab.

Email: bernstei at gmail

Position: I am currently a PostDoc at the Technical University of Berlin, where I am 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, fault-tolerant algorithms, and approximation algorithms.

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

  • Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. (With Sepehr Assadi, MohammadHossein Bateni, Vahab Mirrokni,  Cliff Stein)
    Manuscript  [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 
  • Incremental Topological Sort and Cycle Detection in O(m\sqrt{n}) Expected Total Time. (With Shiri Chechik)
    Accepted to Symposium on Discrete Algorithms (SODA) 2018 [pdf]
  • 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.