3 citations · 6 across the 11 of their papers we have counts for
13 papers
Finite-Precision Gram-Schmidt Walks
Emile Anand, Jan van den Brand, Peter Chen
The Gram-Schmidt Walk is a randomized vector-balancing algorithm whose subgaussian guarantees support applications in discrepancy, experimental design, and data compression; howeve…
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…
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques
Jan van den Brand, Daniel Zhang
Since the development of efficient linear program solvers in the 80s, all major improvements for solving multi-commodity flows to high accuracy came from improvements to general li…
Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
Jan van den Brand, Zhao Song, Tianyi Zhou
Large language models (LLMs) have made fundamental changes in human life. The attention scheme is one of the key components over all the LLMs, such as BERT, GPT-1, Transformers, GP…
Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary
Anastasiia Alokhina, Jan van den Brand
Algebraic data structures are the main subroutine for maintaining distances in fully dynamic graphs in subquadratic time. However, these dynamic algebraic algorithms generally cann…
Nearly Optimal Communication and Query Complexity of Bipartite Matching
Joakim Blikstad, Jan van den Brand, Yuval Efron +2
We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AN…
Weil-Poincaré series and topology of collections of valuations on rational double points
A. Campillo, F. Delgado, S. M. Gusein-Zade
Earlier it was described to which extent the Alexander polynomial in several variables of an algebraic link in the Poincaré sphere determines the topology of the link. It was shown…
Fast Deterministic Fully Dynamic Distance Approximation
Jan van den Brand, Sebastian Forster, Yasamin Nazari
In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain imp…