Faster fully dynamic matchings with small approximation ratios A Bernstein, C Stein Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete …, 2016 | 132 | 2016 |

Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs S Assadi, MH Bateni, A Bernstein, V Mirrokni, C Stein Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019 | 125 | 2019 |

A nearly optimal oracle for avoiding failed vertices and edges A Bernstein, D Karger Proceedings of the forty-first annual ACM symposium on Theory of computing …, 2009 | 113 | 2009 |

Fully dynamic matching in bipartite graphs A Bernstein, C Stein Automata, Languages, and Programming: 42nd International Colloquium, ICALP …, 2015 | 108 | 2015 |

Maintaining shortest paths under deletions in weighted directed graphs A Bernstein Proceedings of the forty-fifth annual ACM symposium on Theory of computing …, 2013 | 93 | 2013 |

Fully dynamic (2+ ε) approximate all-pairs shortest paths with fast query and close to linear update time A Bernstein 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 693-702, 2009 | 91 | 2009 |

A deamortization approach for dynamic spanner and dynamic maximal matching A Bernstein, S Forster, M Henzinger ACM Transactions on Algorithms (TALG) 17 (4), 1-51, 2021 | 76 | 2021 |

Improved dynamic algorithms for maintaining approximate shortest paths under deletions A Bernstein, L Roditty Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete …, 2011 | 76 | 2011 |

A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs A Bernstein Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete …, 2010 | 64 | 2010 |

Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing A Bernstein, MP Gutenberg, T Saranurak 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020 | 61 | 2020 |

Online Bipartite Matching with Amortized *O*(log ^{2} *n*) ReplacementsA Bernstein, J Holm, E Rotenberg Journal of the ACM (JACM) 66 (5), 1-23, 2019 | 61 | 2019 |

Deterministic decremental single source shortest paths: beyond the o (mn) bound A Bernstein, S Chechik Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016 | 61 | 2016 |

Deterministic decremental sssp and approximate min-cost flow in almost-linear time A Bernstein, MP Gutenberg, T Saranurak 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | 56 | 2022 |

Fully-dynamic graph sparsifiers against an adaptive adversary A Bernstein, J Brand, MP Gutenberg, D Nanongkai, T Saranurak, ... arXiv preprint arXiv:2004.08432, 2020 | 55 | 2020 |

Towards a unified theory of sparsification for matching problems S Assadi, A Bernstein arXiv preprint arXiv:1811.02009, 2018 | 53 | 2018 |

Distributed exact weighted all-pairs shortest paths in near-linear time A Bernstein, D Nanongkai Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019 | 52 | 2019 |

A generative theory of similarity C Kemp, A Bernstein, JB Tenenbaum Proceedings of the 27th annual conference of the cognitive science society …, 2005 | 51 | 2005 |

Improved bounds for matching in random-order streams A Bernstein Theory of Computing Systems, 1-15, 2023 | 46 | 2023 |

Improved distance sensitivity oracles via random sampling A Bernstein, D Karger Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete …, 2008 | 44 | 2008 |

Decremental strongly-connected components and single-source reachability in near-linear time A Bernstein, M Probst, C Wulff-Nilsen Proceedings of the 51st Annual ACM SIGACT Symposium on theory of computing …, 2019 | 41 | 2019 |