Distributed and Dynamic Graph Algorithms and Complexity
Acknowledgment: This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 715672.
OVERVIEW
Graph data such as social networks are, like other modern big data, sheer in volume, come from a variety of sources, and evolve at a high velocity. To deal with such data, traditionally fast algorithms, i.e. those that can quickly process a static graph data on a single machine, are no longer considered sufficient. Instead, an algorithm must be distributed, so that it can handle graph data stored at multiple machines, and dynamic, so that it can handle rapid changes. Different aspects of distributed and dynamic algorithms have long been studied by different subfields of computer science. Among the most important ones are:
Communication rounds: The number of rounds needed for machines to communicate to process graph data distributively stored across machines. This is a central subject of study in the area of distributed algorithms.
Update time: The time needed for a single machine to process updates (e.g. insertions and deletions of nodes and edges) in order to maintain some knowledge about the graph. This is the main subject in the area of dynamic algorithms.
The general goal of this project is to advance our understanding of these aspects of distributed and dynamic algorithms. The plan is to develop a systematic, unified, approach to study these algorithms by focusing on solving a few selected problems that are known to be hard against both distributed and dynamic algorithms.
For more information about the project, see the fact sheet at europa.edu.
PROJECT MEMBERS
Primary Investigator
Danupon Nanongkai: Professor, University of Copenhagen and Associate professor, KTH.
Current Members
Sagnik Mukhopadhyay: Postdoc, KTH. Supported between 2019-present.
Mohit Daga: PhD Student, KTH. Supported between 2019-present.
Joakim Blikstad: PhD Student, KTH. Supported between 2020-present.
Former Members
Thatchaphol Saranurak: PhD Student, KTH. Supported between 2016-2018.
Michele Scquizzato: Postdoc, KTH. Supported between 2017-2018.
Jan van den Brand: PhD Student, KTH. Supported between 2017- August 2021.
SELECTED ACTIVITIES
For all activities of group members (travels, publications, visitors, etc.), see the News page.
Course: Danupon lectured at 19th Max Planck Advanced Course on the Foundations of Computer Science in Saarbrücken, Germany, which covered some dynamic algorithms and complexity studied in this project.
Survey: Danupon gave a survey talk at Highlights of Algorithms 2018 in Amsterdam, the Netherlands, which covered some dynamic algorithms and complexity studied in this project.
ALL PUBLICATIONS
Unless stated otherwise, author names are in alphabetical order.
2022
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
Negative-Weight Single-Source Shortest Paths in Almost-linear Time. FOCS 2022
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
Nearly Optimal Communication and Query Complexity of Bipartite Matching. FOCS 2022
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
Cut query algorithms with star contraction. FOCS 2022
Sublinear-round Parallel Matroid Intersection
Joakim Blikstad ICALP 2022 (Best student paper award)
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai ICALP 2022
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun ICALP 2022
Faster Connectivity in Low-rank Hypergraphs via Expander Decomposition
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai. IPCO 2022
2021
Minimum Cuts in Directed Graphs via Partial Sparsification
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud, Thatchaphol Saranurak. FOCS 2021
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs, SPAA 2021
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Vertex Connectivity in Poly-logarithmic Max-flows. STOC 2021
Joakim Blikstad, Jan van den Brand, Danupon Nanongkai, Sagnik Mukhopadhyay
Breaking the Quadratic Barrier for Matroid Intersection. STOC 2021
Michal Dory, Yuval Efron, Danupon Nanongkai, Sagnik Mukhopadhyay
Distributed Weighted Min-Cut in Nearly-Optimal Time. STOC 2021
Joakim Blikstad
Breaking O(nr) for Matroid Intersection, ICALP 2021
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
Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein:
Training (Overparametrized) Neural Networks in Near-Linear Time. ITCS 2021
Jan van den Brand
Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms. SOSA 2021
Best paper award
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time. SODA 2021
2020
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. FOCS 2020
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. FOCS 2020. CoRR abs/1910.08025
Jan van den Brand,Yin Tat Lee, Aaron Sidford and Zhao Song:
Solving Tall Dense Linear Programs in Nearly Linear Time, STOC 2020
Sagnik Mukhopadhyay, Danupon Nanongkai:
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms, STOC 2020
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. SODA 2020
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
Coarse-Grained Complexity for Dynamic Algorithms SODA 2020
Jan van den Brand
A Deterministic Linear Program Solver in Current Matrix Multiplication Time. SODA 2020
2019
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai:
A New Deterministic Algorithm for Dynamic Set Cover. FOCS 2019
Jan van den Brand, Danupon Nanongkai:
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time. FOCS 2019
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak:
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. FOCS 2019
Jan van den Brand, Thatchaphol Saranurak
Sensitive Distance and Reachability Oracles for Large Batch Updates. FOCS 2019.
Danupon Nanongkai, Michele Scquizzato:
Equivalence Classes and Conditional Hardness in Massively Parallel Computations. OPODIS 2019
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof:
New Tools and Connections for Exponential-Time Approximation. Algorithmica 81(10): 3993-4009 (2019)
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai:
Breaking quadratic time for small vertex connectivity and an approximation scheme. STOC 2019: 241-252
Aaron Bernstein, Danupon Nanongkai:
Distributed exact weighted all-pairs shortest paths in near-linear time. STOC 2019: 334-342
Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak:
Distributed edge connectivity in sublinear time. STOC 2019: 343-354
Thatchaphol Saranurak, Di Wang:
Expander Decomposition and Pruning: Faster, Stronger, and Simpler. SODA 2019: 2616-2635
2018
Sebastian Forster, Danupon Nanongkai:
A Faster Distributed Single-Source Shortest Paths Algorithm. FOCS 2018: 686-697
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai:
Dynamic Algorithms for Graph Coloring. SODA 2018: 1-20
László Kozma, Thatchaphol Saranurak:
Smooth heaps and a dual view of self-adjusting data structures. STOC 2018: 801-814
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak:
Multi-Finger Binary Search Trees. ISAAC 2018: 55:1-55:26
Gopal Pandurangan, Peter Robinson, Michele Scquizzato:
On the Distributed Complexity of Large-Scale Graph Computations. SPAA 2018: 405-414
2017
Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak:
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds. FOCS 2017: 168-179
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan:
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS 2017: 743-754
Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen:
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. FOCS 2017: 950-961
Danupon Nanongkai, Thatchaphol Saranurak:
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time. STOC 2017: 1122-1129