Jan van den Brand

About me

I am an Assistant Professor at the School of Computer Science at Georgia Tech. Previously, I was a visiting researcher at the Max Planck Institute for Informatics and a Simons-Berkeley Postdoctoral Researcher. I completed my PhD at KTH in Stockholm, Sweden, under supervision of Danupon Nanongkai. For my PhD thesis I received the EATCS Distinguished Dissertation Award, and SMC Prize for Excellent Doctoral Dissertation. I completed my BSc + MSc at the Goethe University in Frankfurt, Germany.

My research is supported by the National Science Foundation (NSF), and my project "CAREER: From Dynamic Algorithms to Fast Optimization and Back" received an NSF CAREER Award.

Research Interests

My research is on the design and theoretical analysis of efficient algorithms and data structures.
One research focus are dynamic algorithms (i.e., data structures) that maintain properties of dynamically changing graphs and matrices. These can be abstract problems like maintaining the solution of a linear system that changes over time, but it also covers applications like maintaining the fastest route in a road network under changing traffic conditions.
Another research focus are optimization algorithms. Many of these algorithms are iterative and solve a sequence of smaller subproblems, whose solution can be maintained via the aforementioned dynamic algorithms. I develop new iterative methods and dynamic algorithms that complement each other, resulting in improved optimization algorithms.

Many of my results use fast matrix multiplication which is why I created a small tool to obtain upper bounds of such algebraic algorithms.

Students

Papers and Publications

• Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
  with Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva.
  FOCS 2024. [Arxiv]
• The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
  with Emile Anand, Mehrdad Ghadiri, Daniel Zhang.
  ICALP 2024. [Arxiv]
• Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
  with Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford.
  SODA 2024. [Arxiv]
• Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary
  with Anastasiia Alokhina.
  SODA 2024. [Arxiv]
• On Dynamic Graph Algorithms with Predictions
  with Sebastian Forster, Yasamin Nazari, and Adam Polak.
  SODA 2024. [Arxiv]
• Deterministic Fully Dynamic SSSP and More
  with Adam Karczmarz.
  FOCS 2023. [Arxiv]
• A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
  with Li Chen, Maximilian Probst Gutenberg, Rasmus Kyng, Yang P. Liu, Richard Peng, Sushant Sachdeva, Aaron Sidford.
  FOCS 2023. [Arxiv]
• Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques
  with Daniel J. Zhang.
  FOCS 2023. [Arxiv]
• Dynamic Maxflow via Dynamic Interior Point Methods
  with Yang P. Liu and Aaron Sidford.
  STOC 2023. [Arxiv]
• Nearly Optimal Communication and Query Complexity of Bipartite Matching
  with Joakim Blikstad, Yuval Efron, Sagnik Mukhopadhyay and Danupon Nanongkai.
  FOCS 2022. [Arxiv] [IEEE]
• Fast Deterministic Fully Dynamic Distance Approximation
  with Sebastian Forster and Yasamin Nazari.
  FOCS 2022. [Arxiv] [IEEE]
• Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
  with Aaron Bernstein, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford and He Sun.
  ICALP 2022. [Arxiv] [DROPS]
• Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
  with Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng and Aaron Sidford.
  STOC 2022. [Arxiv] [ACM]
• Minimum Cost Flows, MDPs, and L1-Regression in Nearly Linear Time for Dense Instances
  with Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song and Di Wang.
  STOC 2021. [Arxiv] [ACM]
• Breaking the Quadratic Barrier for Matroid Intersection
  with Joakim Blikstad, Sagnik Mukhopadhyay and Danupon Nanongkai.
  STOC 2021. [Arxiv] [ACM]
• Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms
  SOSA 2021, Best Paper. [Arxiv] [SIAM]
• Training (Overparameterized) Neural Networks in Near-Linear Time
  with Binghui Peng, Zhao Song and Omri Weinstein.
  ITCS 2021. [Arxiv] [DROPS]
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
  with Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song and Di Wang.
  FOCS 2020. Invited to the special issue [Arxiv] [IEEE]
• Solving Tall Dense Linear Programs in Nearly Linear Time
  with Yin Tat Lee, Aaron Sidford and Zhao Song.
  STOC 2020. Invited to the special issue [Arxiv] [ACM]
• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
  SODA 2020. [Arxiv] [SIAM]
• Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
  with Danupon Nanongkai.
  FOCS 2019. [Arxiv] [IEEE]
• Sensitive Distance and Reachability Oracles for Large Batch Updates
  with Thatchaphol Saranurak.
  FOCS 2019. [Arxiv] [IEEE]
• Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
  with Danupon Nanongkai and Thatchaphol Saranurak.
  FOCS 2019. [Arxiv] [IEEE]
• Instance-Level Segmentation of Vehicles by Deep Contours
  with Matthias Ochs and Rudolf Mester.*
  ACCV Workshop 2016. [Springer]

Short Biography

• 2022 - current
  Assistant Professor, Georgia Institute of Technology (Georgia Tech)
• 2022
  Visiting researcher, Max Planck Institute for Informatics.
• 2021 - 2022
  Postdoc, Simons Institute & UC Berkeley.
• 2017 - 2021
  PhD (Theoretical Computer Science), KTH Stockholm,
  Advisor Danupon Nanongkai.
• 2015 - 2017
  Master of Science (Mathematics), Goethe University Frankfurt,
  Advisor Amin Coja-Oghlan.
• 2014 - 2016
  Master of Science (Computer Science), Goethe University Frankfurt,
  Advisor Rudolf Mester.
• 2011 - 2016
  Bachlor of Science (Mathematics), Goethe University Frankfurt,
  Advisor Claus P. Schnorr.
• 2011 - 2014
  Bachlor of Science (Computer Science), Goethe University Frankfurt,
  Advisor David Sabel.