
Deterministic Decremental SSSP and Approximate MinCost Flow in AlmostLinear Time
In the decremental singlesource shortest paths problem, the goal is to ...
read it

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Let G = (V,E,w) be a weighted, digraph subject to a sequence of adversar...
read it

Improved Bounds for Distributed Load Balancing
In the load balancing problem, the input is an nvertex bipartite graph ...
read it

Improved Bound for Matching in RandomOrder Streams
We study the problem of computing an approximate maximum cardinality mat...
read it

FullyDynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
read it

NearOptimal Decremental SSSP in Dense Weighted Digraphs
In the decremental SingleSource Shortest Path problem (SSSP), we are gi...
read it

Decremental StronglyConnected Components and SingleSource Reachability in NearLinear Time
Computing the StronglyConnected Components (SCCs) in a graph G=(V,E) is...
read it

Distributed Exact Weighted AllPairs Shortest Paths in NearLinear Time
In the distributed allpairs shortest paths problem (APSP), every node ...
read it

Towards a Unified Theory of Sparsification for Matching Problems
In this paper, we present a construction of a `matching sparsifier', tha...
read it

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
Many dynamic graph algorithms have an amortized update time, rather than...
read it

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Randomized composable coresets were introduced recently as an effective ...
read it
Aaron Bernstein
is this you? claim profile