6 papers
Dynamic Rank, Basis, and Matching
Jan van den Brand, Vishal Kumar, Daniel J. Zhang
We study dynamic algorithms for maintaining fundamental algebraic properties of matrices, specifically, rank, basis, and full-rank submatrices, with applications to maximum matchin…
Computing Flows in Subquadratic Space
Jan van den Brand, Zhao Song, Albert Weng
Space complexity is a critical factor in various computational models, including streaming, parallel/distributed computing, and communication complexity. We study the space complex…
Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang +1
For -vertex -edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with $\tilde O(m…
The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
Emile Anand, Jan van den Brand, Mehrdad Ghadiri +1
Many iterative algorithms in optimization, computational geometry, computer algebra, and other areas of computer science require repeated computation of some algebraic expression w…
Deterministic Fully Dynamic SSSP and More
Jan van den Brand, Adam Karczmarz
We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2…
On Dynamic Graph Algorithms with Predictions
Jan van den Brand, Sebastian Forster, Yasamin Nazari +1
We study dynamic algorithms in the model of algorithms with predictions. We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predic…