Aaron Bernstein

92 papers A* 35A 8Journal 43Unranked 3
YearRankTypeTitle / Venue / Authors
2026 J jnl
Bounding the Fragmentation of B-Trees Subject to Batched Insertions.
CoRR
Michael A. Bender, Aaron Bernstein, Nairen Cao, Alexander Conway, Martín Farach-Colton, Hanna Komlós, Yarin Shechter, Nicole Wein
2026 A* conf
From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction.
SODA
Aaron Bernstein, Jiale Chen
2026 A* conf
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems.
SODA
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
2025 A* conf
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs.
FOCS
Aaron Bernstein, Joakim Blikstad, Jason Li, Thatchaphol Saranurak, Ta-Wei Tu
2025 J jnl
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs.
CoRR
Aaron Bernstein, Joakim Blikstad, Jason Li, Thatchaphol Saranurak, Ta-Wei Tu
2025 A* conf
Deterministic Dynamic Maximal Matching in Sublinear Update Time.
STOC
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2025 J jnl
Deterministic Dynamic Maximal Matching in Sublinear Update Time.
CoRR
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
2025 A* conf
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs.
SODA
Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz
2025 J jnl
From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction.
CoRR
Aaron Bernstein, Jiale Chen
2025 A conf
Low Sensitivity Hopsets.
ITCS
Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, Nicole Wein
2025 A* conf
Matching Composition and Efficient Weight Reduction in Dynamic Matching.
SODA
Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, Ta-Wei Tu
2025 J jnl
Negative-Weight Single-Source Shortest Paths in Near-Linear Time.
Commun. ACM
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2025 J jnl
Negative-Weight Single-Source Shortest Paths in Near-linear Time.
J. ACM
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2025 J jnl
Reviving Thorup's Shortcut Conjecture.
CoRR
Aaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller
2025 J jnl
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems.
CoRR
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
2025 A* conf
Streaming and Communication Complexity of Load-Balancing via Matching Contractors.
SODA
Sepehr Assadi, Aaron Bernstein, Zachary Langley, Lap Chi Lau, Robert Wang
2024 A conf
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?
ITCS
Aaron Bernstein, Greg Bodwin, Nicole Wein
2024 J jnl
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs.
CoRR
Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz
2024 J jnl
Improved Bounds for Matching in Random-Order Streams.
Theory Comput. Syst.
Aaron Bernstein
2024 J jnl
Low Sensitivity Hopsets.
CoRR
Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, Nicole Wein
2024 J jnl
Matching Composition and Efficient Weight Reduction in Dynamic Matching.
CoRR
Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, Ta-Wei Tu
2024 A* conf
Maximum Flow by Augmenting Paths in n
FOCS
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu
2024 J jnl
Maximum Flow by Augmenting Paths in n
CoRR
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu
2024 A conf
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights.
ESA
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
2024 J jnl
Streaming and Communication Complexity of Load-Balancing via Matching Contractors.
CoRR
Sepehr Assadi, Aaron Bernstein, Zachary Langley, Lap Chi Lau, Robert Wang
2023 A conf
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method.
ITCS
Sepehr Assadi, Aaron Bernstein, Zachary Langley
2023 J jnl
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method.
CoRR
Sepehr Assadi, Aaron Bernstein, Zachary Langley
2023 J jnl
Are there graphs whose shortest path structure requires large edge weights?
CoRR
Aaron Bernstein, Greg Bodwin, Nicole Wein
2023 A* conf
Closing the Gap Between Directed Hopsets and Shortcut Sets.
SODA
Aaron Bernstein, Nicole Wein
2023 J jnl
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights.
CoRR
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
2022 J jnl
Closing the Gap Between Directed Hopsets and Shortcut Sets.
CoRR
Aaron Bernstein, Nicole Wein
2022 A* conf
Decremental Matching in General Graphs.
ICALP
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
2022 J jnl
Decremental Matching in General Graphs.
CoRR
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
2022 J jnl
Dynamic Graph Algorithms (Dagstuhl Seminar 22461).
Dagstuhl Reports
Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, Nicole Wein
2022 A* conf
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
ICALP
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2022 J jnl
General bounds for incremental maximization.
Math. Program.
Aaron Bernstein, Yann Disser, Martin Groß, Sandra Himburg
2022 J jnl
Negative-Weight Single-Source Shortest Paths in Almost-linear Time.
CoRR
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2022 A* conf
Negative-Weight Single-Source Shortest Paths in Near-linear Time.
FOCS
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2021 J jnl
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.
ACM Trans. Algorithms
Aaron Bernstein, Sebastian Forster, Monika Henzinger
2021 A* conf
A framework for dynamic matching in weighted graphs.
STOC
Aaron Bernstein, Aditi Dudeja, Zachary Langley
2021 A* conf
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.
FOCS
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2021 J jnl
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.
CoRR
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2021 A conf
Incremental SCC Maintenance in Sparse Graphs.
ESA
Aaron Bernstein, Aditi Dudeja, Seth Pettie
2020 A* conf
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.
FOCS
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2020 J jnl
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.
CoRR
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2020 J jnl
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
CoRR
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2020 J jnl
Improved Bound for Matching in Random-Order Streams.
CoRR
Aaron Bernstein
2020 A conf
Improved Bounds for Distributed Load Balancing.
DISC
Sepehr Assadi, Aaron Bernstein, Zachary Langley
2020 J jnl
Improved Bounds for Distributed Load Balancing.
CoRR
Sepehr Assadi, Aaron Bernstein, Zachary Langley
2020 A* conf
Improved Bounds for Matching in Random-Order Streams.
ICALP
Aaron Bernstein
2020 A* conf
Near-Optimal Decremental SSSP in Dense Weighted Digraphs.
FOCS
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 J jnl
Near-Optimal Decremental SSSP in Dense Weighted Digraphs.
CoRR
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 — conf
Online Matching with Recourse: Random Edge Arrivals.
FSTTCS
Aaron Bernstein, Aditi Dudeja
2019 A* conf
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.
SODA
Aaron Bernstein, Sebastian Forster, Monika Henzinger
2019 A* conf
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs.
SODA
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein
2019 J jnl
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time.
SIAM J. Comput.
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2019 J jnl
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time.
CoRR
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
2019 A* conf
Decremental strongly-connected components and single-source reachability in near-linear time.
STOC
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
2019 J jnl
Distance-Preserving Graph Contractions.
SIAM J. Discret. Math.
Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny
2019 J jnl
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time.
SIAM J. Comput.
Aaron Bernstein, Danupon Nanongkai
2019 A* conf
Distributed exact weighted all-pairs shortest paths in near-linear time.
STOC
Aaron Bernstein, Danupon Nanongkai
2019 J jnl
Online Bipartite Matching with Amortized
J. ACM
Aaron Bernstein, Jacob Holm, Eva Rotenberg
2019 — conf
Towards a Unified Theory of Sparsification for Matching Problems.
SOSA
Sepehr Assadi, Aaron Bernstein
2018 J jnl
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.
CoRR
Aaron Bernstein, Sebastian Forster, Monika Henzinger
2018 A conf
Distance-Preserving Graph Contractions.
ITCS
Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny
2018 J jnl
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time.
CoRR
Aaron Bernstein, Danupon Nanongkai
2018 A* conf
Incremental Topological Sort and Cycle Detection in Expected Total Time.
SODA
Aaron Bernstein, Shiri Chechik
2018 A* conf
Online Bipartite Matching with Amortized Replacements.
SODA
Aaron Bernstein, Jacob Holm, Eva Rotenberg
2018 J jnl
Towards a Unified Theory of Sparsification for Matching Problems.
CoRR
Sepehr Assadi, Aaron Bernstein
2017 J jnl
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs.
CoRR
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein
2017 A* conf
Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs.
SODA
Aaron Bernstein, Shiri Chechik
2017 A* conf
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs.
ICALP
Aaron Bernstein
2017 J jnl
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs.
CoRR
Aaron Bernstein
2017 A* conf
General Bounds for Incremental Maximization.
ICALP
Aaron Bernstein, Yann Disser, Martin Groß
2017 J jnl
General Bounds for Incremental Maximization.
CoRR
Aaron Bernstein, Yann Disser, Martin Groß
2017 J jnl
Online bipartite matching with amortized $O(\log^2 n)$ replacements.
CoRR
Aaron Bernstein, Jacob Holm, Eva Rotenberg
2017 A conf
Simultaneously Load Balancing for Every p-norm, With Reassignments.
ITCS
Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein
2016 — ch.
Decremental Approximate-APSP in Directed Graphs.
Encyclopedia of Algorithms
Aaron Bernstein
2016 A* conf
Deterministic decremental single source shortest paths: beyond the o(mn) bound.
STOC
Aaron Bernstein, Shiri Chechik
2016 — —
Dynamic Algorithms for Shortest Paths and Matching.
Aaron Bernstein
2016 — ch.
Dynamic Approximate-APSP.
Encyclopedia of Algorithms
Aaron Bernstein
2016 A* conf
Faster Fully Dynamic Matchings with Small Approximation Ratios.
SODA
Aaron Bernstein, Cliff Stein
2016 J jnl
Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs.
SIAM J. Comput.
Aaron Bernstein
2015 — conf
Fully Dynamic Matching in Bipartite Graphs.
ICALP (1)
Aaron Bernstein, Cliff Stein
2015 J jnl
Fully Dynamic Matching in Bipartite Graphs.
CoRR
Aaron Bernstein, Clifford Stein
2013 A* conf
Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract].
STOC
Aaron Bernstein
2012 A* conf
Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs.
SODA
Aaron Bernstein
2011 A* conf
Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions.
SODA
Aaron Bernstein, Liam Roditty
2010 A* conf
A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs.
SODA
Aaron Bernstein
2009 A* conf
A nearly optimal oracle for avoiding failed vertices and edges.
STOC
Aaron Bernstein, David R. Karger
2009 A* conf
Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time.
FOCS
Aaron Bernstein
2008 A* conf
Improved distance sensitivity oracles via random sampling.
SODA
Aaron Bernstein, David R. Karger