92 citations · 480 across the 54 of their papers we have counts for
68 papers · 1 filter
Rectangular Matrix Multiplication in the Low-Bandwidth Model
Chetan Gupta, Jukka Suomela, Hossein Vahidi
We study rectangular matrix multiplication in the low-bandwidth model of distributed computing. There are computers; initially the input matrices are distributed evenly between…
Meta-Theorems for Cuttable Distributed Problems
Marthe Bonamy, Avinandan Das, Cyril Gavoille +3
We prove that given any -approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an -round -approximation LOCAL algorithm…
2-Coloring Cycles in One Round
Maxime Flin, Alesya Raevskaya, Ronja Stimpert +2
We show that there is a one-round randomized distributed algorithm that can 2-color cycles such that the expected fraction of monochromatic edges is less than 0.24118. We also show…
Classification of Local Optimization Problems in Directed Cycles
Thomas Boudier, Fabian Kuhn, Augusto Modanese +2
We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOC…
Is a LOCAL algorithm computable?
Antonio Cruciani, Avinandan Das, Massimo Equi +4
Common definitions of the "standard" LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a comput…
It does not matter how you define locally checkable labelings
Antonio Cruciani, Avinandan Das, Alesya Raevskaya +1
Locally checkable labeling problems (LCLs) form the foundation of the modern theory of distributed graph algorithms. First introduced in the seminal paper by Naor and Stockmeyer [S…
On the Universality of Round Elimination Fixed Points
Alkida Balliu, Sebastian Brandt, Ole Gabsdil +2
Recent work on distributed graph algorithms [e.g. STOC 2022, ITCS 2022, PODC 2020] has drawn attention to the following open question: are round elimination fixed points a universa…
Distributed Algorithms for Potential Problems
Alkida Balliu, Thomas Boudier, Francesco d'Amore +4
In this work, we present a fast distributed algorithm for local potential problems: these are graph problems where the task is to find a locally optimal solution where no node can…
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
Alkida Balliu, Corinna Coupette, Antonio Cruciani +6
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no d…
Distributed Quantum Advantage in Locally Checkable Labeling Problems
Alkida Balliu, Filippo Casagrande, Francesco d'Amore +6
In this paper, we present the first known example of a locally checkable labeling problem (LCL) that admits asymptotic distributed quantum advantage in the LOCAL model of distribut…
Distributed Quantum Advantage for Local Problems
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy +10
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prio…
Local problems in trees across a wide range of distributed models
Anubhav Dhar, Eli Kujawa, Henrik Lievonen +4
The randomized online-LOCAL model captures a number of models of computing; it is at least as strong as all of these models: - the classical LOCAL model of distributed graph algori…
Shared Randomness Helps with Local Distributed Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +5
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is loca…
Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
Chetan Gupta, Janne H. Korhonen, Jan Studený +2
In prior work, Gupta et al. (SPAA 2022) presented a distributed algorithm for multiplying sparse matrices, using computers. They assumed that the input matrices ar…
Distributed Computation with Local Advice
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +4
In this work we study local computation with advice: the goal is to solve a graph problem with a distributed algorithm in communication rounds, for some function tha…
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore +8
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-s…
Distributed Binary Labeling Problems in High-Degree Graphs
Henrik Lievonen, Timothé Picavet, Jukka Suomela
Balliu et al. (DISC 2020) classified the hardness of solving binary labeling problems with distributed graph algorithms; in these problems the task is to select a subset of edges i…
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala +7
We give an almost complete characterization of the hardness of -coloring -chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. I…
Distributed derandomization revisited
Sameep Dahal, Francesco d'Amore, Henrik Lievonen +2
One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves…
Fast Dynamic Programming in Trees in the MPC Model
Chetan Gupta, Rustam Latypov, Yannic Maus +6
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in rounds in the massively parallel computation model (MPC), with…
Mending Partial Solutions with Few Changes
Darya Melnyk, Jukka Suomela, Neven Villani
In this paper, we study the notion of mending, i.e. given a partial solution to a graph problem, we investigate how much effort is needed to turn it into a proper solution. For exa…
Sparse Matrix Multiplication in the Low-Bandwidth Model
Chetan Gupta, Juho Hirvonen, Janne H. Korhonen +2
We study matrix multiplication in the low-bandwidth model: There are computers, and we need to compute the product of two matrices. Initially computer knows ro…
Efficient Classification of Locally Checkable Problems in Regular Trees
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +3
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[Θ(\log n), Θ(n)…
Sinkless Orientation Made Simple
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn +9
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distribut…