8 papers
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…
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,…
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…