8 papers
DejaVu: A Minimalistic Mechanism for Distributed Plurality Consensus
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +2
We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of opinions, aims to agree on the init…
Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
Arthur da Cunha, Francesco d'Amore, Emanuele Natale
The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised neural networks likely contain subnetworks that perform well without any training. Although unstructure…
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…
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…
On the -majority dynamics with many opinions
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +1
We present the first upper bound on the convergence time to consensus of the well-known -majority dynamics with opinions, in the synchronous setting, for and that ar…
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…