12 citations · 36 across the 12 of their papers we have counts for
14 papers
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, Rasmus Kyng +4
We give the first almost-linear total time algorithm for deciding if a flow of cost at most still exists in a directed graph, with edge costs and capacities, undergoing decreme…
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Jan van den Brand, Li Chen, Rasmus Kyng +5
We provide an algorithm which, with high probability, maintains a -approximate maximum flow on an undirected graph undergoing -edge additions in amortized $m^{o(1)} ε^{-3…
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
Jan van den Brand, Li Chen, Rasmus Kyng +5
We give a deterministic time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral dem…
Dynamic Maxflow via Dynamic Interior Point Methods
Jan van den Brand, Yang P. Liu, Aaron Sidford
In this paper we provide an algorithm for maintaining a -approximate maximum flow in a dynamic, capacitated graph undergoing edge additions. Over a sequence of -additions…
Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms
Jan van den Brand
Many algorithms use data structures that maintain properties of matrices undergoing some changes. The applications are wide-ranging and include for example matchings, shortest path…
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai +5
We present an -time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, a…
Training (Overparametrized) Neural Networks in Near-Linear Time
Jan van den Brand, Binghui Peng, Zhao Song +1
The slow convergence rate and pathological curvature issues of first-order gradient methods for training deep neural networks, initiated an ongoing effort for developing faster $\m…
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,…
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford +1
In this paper we provide an time randomized algorithm for solving linear programs with variables and constraints with high probability. To obtain this…
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
Jan van den Brand, Danupon Nanongkai
Consider the following distance query for an -node graph undergoing edge insertions and deletions: given two sets of nodes and , return the distances between every pa…
A Deterministic Linear Program Solver in Current Matrix Multiplication Time
Jan van den Brand
Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linea…
Sensitive Distance and Reachability Oracles for Large Batch Updates
Jan van den Brand, Thatchaphol Saranurak
In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph with nodes and integer weights from . Second, given a s…
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynam…
The Mutual information of LDGM codes
Jan van den Brand, Nor Jaafari
We provide matching upper and lower bounds on the mutual information in noisy reconstruction of parity check codes and thereby prove a long-standing conjecture by Montanari [IEEE T…