AMG is a one-day workshop that focuses on algorithms for big data and large graphs. The program consists of four invited talks, which are aimed at the general DISC audience.

AMG 2022 will be held on Friday, 28 October 2022, and will be co-located with DISC 2022. It will be possible to attend the workshop either as an online conference via Zoom or as a physical event at Augusta, Georgia (USA). For information about the registration, please go to the DISC 2022 registration page. The workshop will be chaired by Shreyas Pai.


All times in Eastern Daylight Time (EDT) GMT-4.

AMG programme
10:30 - 11:30 talk 1 Jakub Łącki: Massively Parallel Computation: Theory and Practice (Slides)
11:30 - 12:00 Coffee break
12:00 - 13:00 talk 2 Sam Coy: Connectivity and Spanning Forest Problems in MPC (Slides)
13:00 - 14:00 Lunch break
14:00 - 15:00 talk 3 Peter Davies: Lower Bounds in Massively Parallel Computation (Slides)
15:00 - 16:00 talk 4 Yasamin Nazari: Distance Computation in MPC and Related Models
16:00 Workshop ends

Invited Speakers

[Jakub Łącki]

Jakub Łącki

Google Research

Jakub Łącki is a research scientist working on graph-mining and large-scale optimization teams. He received his PhD from Univeristy of Warsaw in 2015, advised by Piotr Sankowski. Before joining Google he was a postdoctoral researcher at Sapienza University of Rome, working with Stefano Leonardi.

Title: Foraging in Particle Systems via Self-Induced Phase Changes (Slides)

Abstract: The Massively Parallel Computation (MPC) model was inspired by several modern distributed computation frameworks, including MapReduce and Pregel. In this talk we compare the MPC model with the computation frameworks it captures and discuss how it relates to practical large-scale computation. Moreover, we present an extension of the MPC model, called Adaptive Massively Parallel Computation (AMPC), which models a combination of MapReduce and a distributed key-value store. We show that AMPC admits constant-round algorithms for several prominent algorithmic problems, and the corresponding implementations are highly effective in practice.

[Sam Coy]

Sam Coy

Univeristy of Warwick

Sam Coy is a fourth year Computer Science PhD student studying at the Department of Computer Science at the University of Warwick. His supervisor is Artur Czumaj. His undergraduate study took place in the same department and he graduated with an MEng in 2019. He is part of the Theory and Foundations group.

Title: Connectivity and Spanning Forest Problems in MPC (Slides)

Abstract: Connectivity, spanning forest, and minimum spanning tree are fundamental algorithmic problems. They are used as subroutines in many algorithmic settings, and so it is especially important that algorithms for these problems be as fast as possible.

A recent line of research in the Massively Parallel Computation (MPC) model, with low local space per machine, has led to a significant improvement in the complexity of the state-of-the-art algorithms for these problems; and further work derandomized these algorithms without any asymptotic loss of complexity. Additionally, recent research has led to conditional lower bounds for connectivity and spanning tree which nearly match the complexity of the best known algorithms.

In this talk, we discuss this line of work, the techniques and challenges involved, and conclude with a discussion of interesting open problems.

[Peter Davies]

Peter Davies

University of Durham

Peter Davies is an Assistant Professor at Durham University, in the Network Engineering Science and Theory in Durham (NESTiD) group. Previously, he was a lecturer at the University of Surrey, in the Distributed and Networked Systems Group, and before that he did postdocs in Dan Alistarh's group at IST Austria, and with Artur Czumaj at the University of Warwick.

Title: Lower Bounds in Massively Parallel Computation (Slides)

Abstract: The Massively Parallel Computation model has risen to popularity in recent years, accompanied by an array of very fast algorithms for classic graph problems. Until recently, however, no meaningful lower bounds for the model were known. While there is evidence that we cannot currently hope for unconditional lower bounds, a framework introduced by Ghaffari, Kuhn and Uitto (FOCS ’19) and revised by Czumaj, Davies and Parter (PODC ’21) allowed a host of lower bounds from the LOCAL model to be transferred to low-space MPC, conditioned on the hardness of a simple connectivity problem.

However, the latter also showed that these bounds are subject to some important technical caveats relating to the concept of “component-stability”, and that in some cases they can be surpassed by component-unstable algorithms. In this talk, we will survey the current status of lower bounds in low-space MPC, where they do and do not hold, and whether there is scope to find more robust bounds.

[Yasamin Nazari]

Yasamin Nazari

University of Salzburg

Yasamin Nazari is a postdoctoral researcher at University of Salzburg, working with Dr. Sebastian Forster. She completed her PhD at Johns Hopkins University, Computer Science Department, where she was advised by Dr. Mike Dinitz. She received her Master's degree from University of Calgary, under supervision of Dr. Philipp Woelfel and Dr. George Giakkoupis, and her undergraduate degree from Shiraz University of Technology, Iran.

Title: Distance Computation in MPC and Related Models

Abstract: Even though the MPC model is expected to be much more powerful than distributed models such as the local or congest models, so far most of a vast majority of results in this model are limited to local problems. Shortest path computation is one of the most fundamental examples of such global problems that is still quite challenging in MPC, specially in the more restrictive low memory settings. In this talk I explain some directions for tackling this important problem using distance structures such as spanners, hopsets and distance sketches. I will also explain how these objects are used in related models (such as PRAM and Congested Clique) and describe the obstacles we face in getting faster MPC algorithms using the existing algorithmic toolkit.