Aaron Bernstein

According to our database, Aaron Bernstein authored at least 53 papers between 2008 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Improved Bounds for Matching in Random-Order Streams.

Aaron Bernstein

Theory Comput. Syst., August, 2024

Matching Composition and Efficient Weight Reduction in Dynamic Matching.

Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, Ta-Wei Tu

CoRR, 2024

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs.

Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz

CoRR, 2024

Streaming and Communication Complexity of Load-Balancing via Matching Contractors.

Sepehr Assadi, Aaron Bernstein, Zachary Langley, Lap Chi Lau, Robert Wang

CoRR, 2024

Low Sensitivity Hopsets.

Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, Nicole Wein

CoRR, 2024

Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?

Aaron Bernstein, Greg Bodwin, Nicole Wein

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Maximum Flow by Augmenting Paths in n^2+o(1) Time.

Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights.

Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights.

Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su

CoRR, 2023

Closing the Gap Between Directed Hopsets and Shortcut Sets.

Aaron Bernstein, Nicole Wein

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method.

Sepehr Assadi, Aaron Bernstein, Zachary Langley

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Dynamic Graph Algorithms (Dagstuhl Seminar 22461).

Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, Nicole Wein

Dagstuhl Reports, November, 2022

General bounds for incremental maximization.

Aaron Bernstein, Yann Disser, Martin Groß, Sandra Himburg

Math. Program., 2022

Negative-Weight Single-Source Shortest Paths in Almost-linear Time.

Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen

CoRR, 2022

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.

Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Decremental Matching in General Graphs.

Sepehr Assadi, Aaron Bernstein, Aditi Dudeja

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Negative-Weight Single-Source Shortest Paths in Near-linear Time.

Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.

Aaron Bernstein, Sebastian Forster, Monika Henzinger

ACM Trans. Algorithms, 2021

A framework for dynamic matching in weighted graphs.

Aaron Bernstein, Aditi Dudeja, Zachary Langley

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.

Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Incremental SCC Maintenance in Sparse Graphs.

Aaron Bernstein, Aditi Dudeja, Seth Pettie

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Improved Bound for Matching in Random-Order Streams.

Aaron Bernstein

CoRR, 2020

Improved Bounds for Distributed Load Balancing.

Sepehr Assadi, Aaron Bernstein, Zachary Langley

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Online Matching with Recourse: Random Edge Arrivals.

Aaron Bernstein, Aditi Dudeja

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Near-Optimal Decremental SSSP in Dense Weighted Digraphs.

Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.

Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Distance-Preserving Graph Contractions.

Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny

SIAM J. Discret. Math., 2019

Online Bipartite Matching with Amortized <i>O</i>(log ² <i>n</i>) Replacements.

Aaron Bernstein, Jacob Holm, Eva Rotenberg

J. ACM, 2019

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

Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen

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

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

Aaron Bernstein, Danupon Nanongkai

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

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

Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein

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

Towards a Unified Theory of Sparsification for Matching Problems.

Sepehr Assadi, Aaron Bernstein

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

2018

Online Bipartite Matching with Amortized Replacements.

Aaron Bernstein, Jacob Holm, Eva Rotenberg

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

Incremental Topological Sort and Cycle Detection in Expected Total Time.

Aaron Bernstein, Shiri Chechik

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

2017

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

Aaron Bernstein, Jacob Holm, Eva Rotenberg

CoRR, 2017

Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs.

Aaron Bernstein, Shiri Chechik

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

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

Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein

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

General Bounds for Incremental Maximization.

Aaron Bernstein, Yann Disser, Martin Groß

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

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs.

Aaron Bernstein

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

2016

Dynamic Approximate-APSP.

Aaron Bernstein

Encyclopedia of Algorithms, 2016

Decremental Approximate-APSP in Directed Graphs.

Aaron Bernstein

Encyclopedia of Algorithms, 2016

Dynamic Algorithms for Shortest Paths and Matching.

Aaron Bernstein

PhD thesis, 2016

Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs.

Aaron Bernstein

SIAM J. Comput., 2016

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

Aaron Bernstein, Shiri Chechik

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

Faster Fully Dynamic Matchings with Small Approximation Ratios.

Aaron Bernstein, Cliff Stein

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

2015

Fully Dynamic Matching in Bipartite Graphs.

Aaron Bernstein, Cliff Stein

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

2013

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

Aaron Bernstein

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

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

Aaron Bernstein

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

2011

Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions.

Aaron Bernstein, Liam Roditty

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.

Aaron Bernstein

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

2009

A nearly optimal oracle for avoiding failed vertices and edges.

Aaron Bernstein, David R. Karger

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.

Aaron Bernstein

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

2008

Improved distance sensitivity oracles via random sampling.

Aaron Bernstein, David R. Karger

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