Aaron Bernstein

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 59

Top Topics

Top Venues

Publications

Aaron Bernstein, Greg Bodwin, Nicole Wein
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights? ITCS (2024)
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu
Time. CoRR (2024)
Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng, Jie Gao, Nicole Wein
Low Sensitivity Hopsets. CoRR (2024)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. ITCS (2023)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. CoRR (2023)
Aaron Bernstein, Greg Bodwin, Nicole Wein
Are there graphs whose shortest path structure requires large edge weights? CoRR (2023)
Aaron Bernstein, Nicole Wein
Closing the Gap Between Directed Hopsets and Shortcut Sets. SODA (2023)
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights. CoRR (2023)
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
Decremental Matching in General Graphs. CoRR (2022)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. FOCS (2022)
Aaron Bernstein, Yann Disser, Martin Groß, Sandra Himburg
General bounds for incremental maximization. Math. Program. 191 (2) (2022)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. ICALP (2022)
Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, Nicole Wein
Dynamic Graph Algorithms (Dagstuhl Seminar 22461). Dagstuhl Reports 12 (11) (2022)
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
Decremental Matching in General Graphs. ICALP (2022)
Aaron Bernstein, Nicole Wein
Closing the Gap Between Directed Hopsets and Shortcut Sets. CoRR (2022)
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
Negative-Weight Single-Source Shortest Paths in Almost-linear Time. CoRR (2022)
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
Negative-Weight Single-Source Shortest Paths in Near-linear Time. FOCS (2022)
Aaron Bernstein, Sebastian Forster, Monika Henzinger
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. ACM Trans. Algorithms 17 (4) (2021)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. FOCS (2021)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. CoRR (2021)
Aaron Bernstein, Aditi Dudeja, Zachary Langley
A framework for dynamic matching in weighted graphs. STOC (2021)
Aaron Bernstein, Aditi Dudeja, Seth Pettie
Incremental SCC Maintenance in Sparse Graphs. ESA (2021)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. FOCS (2020)
Aaron Bernstein, Aditi Dudeja
Online Matching with Recourse: Random Edge Arrivals. FSTTCS (2020)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. CoRR (2020)
Aaron Bernstein
Improved Bound for Matching in Random-Order Streams. CoRR (2020)
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Near-Optimal Decremental SSSP in Dense Weighted Digraphs. CoRR (2020)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
Improved Bounds for Distributed Load Balancing. CoRR (2020)
Aaron Bernstein
Improved Bounds for Matching in Random-Order Streams. ICALP (2020)
Sepehr Assadi, Aaron Bernstein, Zachary Langley
Improved Bounds for Distributed Load Balancing. DISC (2020)
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Near-Optimal Decremental SSSP in Dense Weighted Digraphs. FOCS (2020)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. CoRR (2020)
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time. CoRR (2019)
Sepehr Assadi, Aaron Bernstein
Towards a Unified Theory of Sparsification for Matching Problems. SOSA (2019)
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
Decremental strongly-connected components and single-source reachability in near-linear time. STOC (2019)
Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny
Distance-Preserving Graph Contractions. SIAM J. Discret. Math. 33 (3) (2019)
Aaron Bernstein, Jacob Holm, Eva Rotenberg
) Replacements. J. ACM 66 (5) (2019)
Aaron Bernstein, Danupon Nanongkai
Distributed exact weighted all-pairs shortest paths in near-linear time. STOC (2019)
Aaron Bernstein, Sebastian Forster, Monika Henzinger
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. SODA (2019)
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. SODA (2019)
Sepehr Assadi, Aaron Bernstein
Towards a Unified Theory of Sparsification for Matching Problems. CoRR (2018)
Aaron Bernstein, Danupon Nanongkai
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time. CoRR (2018)
Aaron Bernstein, Shiri Chechik
Incremental Topological Sort and Cycle Detection in Expected Total Time. SODA (2018)
Aaron Bernstein, Jacob Holm, Eva Rotenberg
Online Bipartite Matching with Amortized Replacements. SODA (2018)
Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny
Distance-Preserving Graph Contractions. ITCS (2018)
Aaron Bernstein, Sebastian Forster, Monika Henzinger
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. CoRR (2018)
Aaron Bernstein, Yann Disser, Martin Groß
General Bounds for Incremental Maximization. CoRR (2017)
Aaron Bernstein, Jacob Holm, Eva Rotenberg
Online bipartite matching with amortized $O(\log^2 n)$ replacements. CoRR (2017)
Aaron Bernstein, Yann Disser, Martin Groß
General Bounds for Incremental Maximization. ICALP (2017)
Aaron Bernstein
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. ICALP (2017)
Aaron Bernstein
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. CoRR (2017)
Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein
Simultaneously Load Balancing for Every p-norm, With Reassignments. ITCS (2017)
Aaron Bernstein, Shiri Chechik
Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs. SODA (2017)
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. CoRR (2017)
Aaron Bernstein, Cliff Stein
Faster Fully Dynamic Matchings with Small Approximation Ratios. SODA (2016)
Aaron Bernstein
Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs. SIAM J. Comput. 45 (2) (2016)
Aaron Bernstein, Shiri Chechik
Deterministic decremental single source shortest paths: beyond the o(mn) bound. STOC (2016)
Aaron Bernstein, Clifford Stein
Fully Dynamic Matching in Bipartite Graphs. CoRR (2015)
Aaron Bernstein, Cliff Stein
Fully Dynamic Matching in Bipartite Graphs. ICALP (1) (2015)
Aaron Bernstein
Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]. STOC (2013)
Aaron Bernstein
Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs. SODA (2012)
Aaron Bernstein, Liam Roditty
Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions. SODA (2011)
Aaron Bernstein
A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs. SODA (2010)
Aaron Bernstein
Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time. FOCS (2009)
Aaron Bernstein, David R. Karger
A nearly optimal oracle for avoiding failed vertices and edges. STOC (2009)
Aaron Bernstein, David R. Karger
Improved distance sensitivity oracles via random sampling. SODA (2008)