Research & Team
RESEARCH INTERESTS
Our long-term vision is to develop cross-paradigm techniques for designing algorithms that work across many models of computation, such as dynamic, distributed, streaming, parallel, and quantum algorithms. Our philosophy is to simultaneously study the same question from the perspectives of many computing paradigms to find new insights that may not emerge from the isolated viewpoint of a single model. We aim to achieve two goals simultaneously: (i) solutions for notorious long-standing open problems and (ii) efficient algorithms that can fully exploit the characteristics of modern computing devices and data.
Our current focus is on basic questions about graph data, such as connectivity, shortest paths, and matching. The aim is to develop provably fast algorithms and complexity theory, using tools such as sketching, spectral techniques, fast matrix multiplication, approximation algorithms, communication complexity and fine-grained complexity.
Although we focus on long-standing open problems and mathematical proofs, we are open to new problems arising from applications and to collaborations with experimentalists.
Keywords: Graph algorithms, Modern computational models, Distributed algorithms, Dynamic algorithms, Approximation algorithms, Sublinear algorithms, Lower bounds, Fine-grained Complexity, Hardness of approximation.
TEAM MEMBERS
Due to the change of my role to directorship, this list might not be actively maintained and will not cover all members in my deparment. See Algorithms & Complexity department webpage at MPI-INF for a more complete list.
Current
Joakim Oscar Blikstad: PhD Student, KTH, 2020-. Google PhD Fellow 2023.
Yonggang Jiang: PhD Student, MPI-INF, 2021-.
Zihang Wu: PhD Student, MPI-INF, 2022-.
Former
Sagnik Mukhopadhyay: Postdoc, KTH, 2019-2021 & Copenhagen 2021 → lecturer at the University of Sheffield
Jan van den Brand: PhD Student, KTH, 2017-2021 → assistant professor at Georgia Tech (with a gap year in Berkeley/Simons Institute)
Stockholm Mathematics Centre Prize for Excellent Doctoral Dissertation 2021/2022
Thatchaphol Saranurak: PhD Student, KTH, 2015-2018 → research assistant professor at TTI-Chicago → assistant professor at University of Michigan, Ann Arbor
NSF CAREER Award 2023
Michele Scquizzato: Postdoc, KTH, 2017-2018 → assistant professor ("Ricercatore") at University of Padova, Italy.
Fei Chen: Postdoc, KTH, 2015-2016 → researcher at Huawei Noah's Ark Lab (Hong Kong).
ACTIVITIES
For activities of group members (travels, publications, visitors, etc.), see the News page.
For Danupon's personal log on conference attendances and PC committees, see the Biography page.
SUPPORTS
We appreciate the funding from
the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 715672, and
the Swedish Research Council (Reg. No. 2019-05622 and 2015-04659).
ADDITIONAL PUBLICATIONS BY TEAM MEMBERS
Below are papers co-authored by team members that are not co-authored by Danupon during their terms in Danupon's team. For papers co-authored by Danupon, see the Publications.
24. Minimum Star Partitions of Simple Polygons in Polynomial Time
Joakim Blikstad (with Mikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen Zhang)
STOC 2024
23. Online Edge-Coloring is (Nearly) as Easy as Offline
Joakim Blikstad (with Ola Svensson, Radu Vintan, David Wajc)
STOC 2024
22. Incremental (1-eps)-approximate dynamic matching in O(poly(1/eps)) update time
Joakim Blikstad and Peter Kiss
ESA 2023 (Best student paper award)
21. Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang (with Sagnik Mukhopadhyay)
STOC 2023
20. Robust and Optimal Contention Resolution without Collision Detection
Yonggang Jiang (with Chaodong Zheng)
SPAA 2022
19. Sublinear-round Parallel Matroid Intersection
Joakim Blikstad
ICALP 2022 (Best student paper award)
18. Breaking O(nr) for Matroid Intersection
Joakim Blikstad
ICALP 2021
Links: 📄arXiv
17. Minimum Cost Flows, MDPs, and L1-Regression in Nearly Linear Time for Dense Instances
Jan van den Brand (with Yin-Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang)
STOC 2021
Links: 📄arXiv
16. Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms
Jan van den Brand
SOSA 2021 (best paper award)
15. Training (Overparametrized) Neural Networks in Near-Linear Time
Jan van den Brand (with Binghui Peng, Zhao Song, Omri Weinstein)
ITCS 2021
Links: 📄arXiv
14. Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand (with Yin Tat Lee, Aaron Sidford and Zhao Song)
STOC 2020 (invited to special issue)
13. A Deterministic Linear Program Solver in Current Matrix Multiplication Time
Jan van den Brand
SODA 2020
Links: 📄arXiv
12. A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
Michele Scquizzato (with Gopal Pandurangan, Peter Robinson)
ACM Transactions on Algorithms 2019
The paper was partially done while M.S. was a postdoc at KTH and published after he moved to the University of Padova.
11. Sensitive Distance and Reachability Oracles for Large Batch Updates
Jan van den Brand (with Thatchaphol Saranurak)
FOCS 2019
Links: 📄pdf
The paper was partially done while T.S. was a PhD student at KTH.
10. Lifting theorems for Equality
Sagnik Mukhopadhyay (with Bruno Loff)
STACS 2019
9. Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Thatchaphol Saranurak (with Di Wang)
SODA 2019
The paper was submitted while T.S. was a PhD student at KTH. The final publication was after he graduated.
8. Multi-finger binary search trees
Thatchaphol Saranurak (with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, László Kozma)
ISAAC 2018
The paper was submitted while T.S. was a PhD student at KTH. The final publication was after he graduated.
7. The Distributed Minimum Spanning Tree Problem
Michele Scquizzato (with Gopal Pandurangan, Peter Robinson)
EATCS Bulletin Issue 125: June 2018
Links: 📄pdf
6. On the Distributed Complexity of Large-Scale Graph Computations
Michele Scquizzato (with Gopal Pandurangan, Peter Robinson)
SPAA 2018
5. Smooth heaps and a dual view of self-adjusting data structures
Thatchaphol Saranurak (with László Kozma)
STOC 2018, SICOMP special issue
4. Beating Ratio 0.5 for Weighted Oblivious Matching Problems
Fei Chen (with Melika Abolhassani, T-H. Hubert Chan, Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Hamid Mahini and Xiaowei Wu)
ESA 2016
3. Pattern-avoiding Access in Binary Search Trees
Thatchaphol Saranurak (with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, and László Kozma)
FOCS 2015
2. Self-Adjusting Binary Search Trees: What Makes Them Tick?
Thatchaphol Saranurak (with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, and László Kozma)
ESA 2015
1. Greedy Is an Almost Optimal Deque
Thatchaphol Saranurak (with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, and László Kozma)
WADS 2015