# Aaron Bernstein

According to our database

Collaborative distances:

^{1}, Aaron Bernstein authored at least 27 papers between 2008 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Distance-Preserving Graph Contractions.

SIAM J. Discrete Math., 2019

J. ACM, 2019

Decremental strongly-connected components and single-source reachability in near-linear time.

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Distributed exact weighted all-pairs shortest paths in near-linear time.

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Towards a Unified Theory of Sparsification for Matching Problems.

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

2018

Online Bipartite Matching with Amortized Replacements.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Incremental Topological Sort and Cycle Detection in Expected Total Time.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Online bipartite matching with amortized $O(\log^2 n)$ replacements.

CoRR, 2017

Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs.

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Simultaneously Load Balancing for Every p-norm, With Reassignments.

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

General Bounds for Incremental Maximization.

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs.

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Dynamic Approximate-APSP.

Encyclopedia of Algorithms, 2016

Decremental Approximate-APSP in Directed Graphs.

Encyclopedia of Algorithms, 2016

Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs.

SIAM J. Comput., 2016

Deterministic decremental single source shortest paths: beyond the o(mn) bound.

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Faster Fully Dynamic Matchings with Small Approximation Ratios.

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Fully Dynamic Matching in Bipartite Graphs.

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2013

Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract].

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs.

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions.

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

A nearly optimal oracle for avoiding failed vertices and edges.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Improved distance sensitivity oracles via random sampling.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008