ERC DisDyn

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