Publications (37)
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz
In the restricted shortest paths problem, we are given a graph whose edges are assigned two non-negative weights: lengths and delays, a source , and a delay threshold . T…
Closing the Gap Between Directed Hopsets and Shortcut Sets
Aaron Bernstein, Nicole Wein
For an n-vertex directed graph , a -\emph{shortcut set} is a set of additional edges such that has the same transitive closur…
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg +4
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees,…
Towards a Unified Theory of Sparsification for Matching Problems
Sepehr Assadi, Aaron Bernstein
In this paper, we present a construction of a `matching sparsifier', that is, a sparse subgraph of the given graph that preserves large matchings approximately and is robust to mod…
Observation of Plasma Bubble Structures in a GeV Laser-Plasma Accelerator
Yen-Yu Chang, Kathleen Weichman, Xiantao Cheng +8
We measure characteristics of plasma bubbles in GeV-class laser-plasma accelerators (LPAs) using Faraday rotation diagnostics. We extend these techniques, previously demonstrated f…
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…
Maximum Flow by Augmenting Paths in Time
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1
We present a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time, whi…
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the weighted load balancing problem, the input is an -vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real w…
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
Aaron Bernstein
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph and a source node the goal is to maintain shortest distances betw…
General Bounds for Incremental Maximization
Aaron Bernstein, Yann Disser, Martin GroÃ
We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardi…
Online Bipartite Matching with Amortized Replacements
Aaron Bernstein, Jacob Holm, Eva Rotenberg
In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all…
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Let be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed sour…
Fully Dynamic Matching in Bipartite Graphs
Aaron Bernstein, Cliff Stein
Maximum cardinality matching in bipartite graphs is an important and well-studied problem. The fully dynamic version, in which edges are inserted and deleted over time has also bee…
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph undergoing edge deletions and a source vertex ; let $n =…
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Are there graphs whose shortest path structure requires large edge weights?
Aaron Bernstein, Greg Bodwin, Nicole Wein
The aspect ratio of a (positively) weighted graph is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in gr…
Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg +1
We present parallel algorithms for computing single-source reachability and shortest paths on directed -vertex -edge graphs using near-linear work and $o(\sqrt…
Decremental Matching in General Graphs
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph , while the adversary makes changes to the edges of the graph. The goal is to…
Distance-preserving graph contractions
Aaron Bernstein, Karl Däubel, Yann Disser +3
Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a…
Low Sensitivity Hopsets
Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng +2
Given a weighted graph , a -hopset is an edge set such that for any , where can reach in , there is a path from to in $G \…
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Aaron Bernstein, Sebastian Forster, Monika Henzinger
Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, wher…
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1
We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an -vertex graph in amortized update time. This breaks the long-standi…
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source to every vertex in an -edge graph undergoing edge deletion…
Distributed Load Balancing on Unrelated Machines
Aaron Bernstein, Anupam Gupta, Zhaozi Wang
We study the well-known load balancing problem in the distributed CONGEST model of computation. We consider the unrelated machines setting, where each job specifies a size $s_{…
Improved Bounds for Distributed Load Balancing
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the load balancing problem, the input is an -vertex bipartite graph and a positive weight for each client . The algorithm must assign each client…
Time-Resolved Pulse Propagation in Glass in Single-Shot
Yen-Yu Chang, Zhengyan Li, James Welch +3
We report time-resolved pulse self-steepening and temporal splitting in flint glass (SF11) in single-shot using broadband frequency-domain streak camera (B-FDSC). The broadband ($6…
Streaming and Communication Complexity of Load-Balancing via Matching Contractors
Sepehr Assadi, Aaron Bernstein, Zachary Langley +2
In the load-balancing problem, we have an -vertex bipartite graph between a set of clients and servers. The goal is to find an assignment of all clients to the ser…
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
Computing the Strongly-Connected Components (SCCs) in a graph is known to take only time using an algorithm by Tarjan from 1972[SICOMP 72] where , $n=…
Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Michael A. Bender, Aaron Bernstein, Nairen Cao +5
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves o…
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein, Danupon Nanongkai
In the {\em distributed all-pairs shortest paths} problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from ever…
Improved Bound for Matching in Random-Order Streams
Aaron Bernstein
We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a \emph{random} order. In the semi-streaming model, t…
Negative-Weight Single-Source Shortest Paths in Near-linear Time
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
We present a randomized algorithm that computes single-source shortest paths (SSSP) in time when edge weights are integral and can be negative. This essential…
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Aaron Bernstein, Jiale Chen, Aditi Dudeja +3
We consider the foundational problem of maintaining a -approximate maximum weight matching (MWM) in an -node dynamic graph undergoing edge insertions and deleti…
From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
Aaron Bernstein, Jiale Chen
We study the approximate maximum weight matching (MWM) problem in a fully dynamic graph subject to edge insertions and deletions. We design meta-algorithms that reduce the problem…
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein +2
As massive graphs become more prevalent, there is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex co…