9 citations · 19 across the 10 of their papers we have counts for
16 papers
Superlogarithmic Gap Result for LCLs on Trees in Quantum-LOCAL
Francesco d'Amore, Henrik Lievonen
We show that, on trees, any locally checkable labeling problem (LCL) that can be solved by an -dependent distribution can also be solved by an -round deter…
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…
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…
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…
On the Limits of Distributed Quantum Computing
Francesco d'Amore
Quantum advantage is well-established in centralized computing, where quantum algorithms can solve certain problems exponentially faster than classical ones. In the distributed set…
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…
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…
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…
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…
On the Multidimensional Random Subset Sum Problem
Luca Becchetti, Arthur Carvalho Walraven da Cunha, Andrea Clementi +4
In the Random Subset Sum Problem, given i.i.d. random variables , we wish to approximate any point as the sum of a suitable subset $X_{i_1(z)}, ..…
Revisiting the Random Subset Sum problem
Arthur da Cunha, Francesco d'Amore, Frédéric Giroire +3
The average properties of the well-known Subset Sum Problem can be studied by the means of its randomised version, where we are given a target value , random variables $X_1, \ld…
Planning with Biological Neurons and Synapses
Francesco d'Amore, Daniel Mitropolsky, Pierluigi Crescenzi +2
We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that…
Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions
Francesco d'Amore, Andrea Clementi, Emanuele Natale
In several real \emph{Multi-Agent Systems} (MAS), it has been observed that only weaker forms of\emph{metastable consensus} are achieved, in which a large majority of agents agree…
Search via Parallel Lévy Walks on
Andrea Clementi, Francesco d'Amore, George Giakkoupis +1
Motivated by the Lévy foraging hypothesis -- the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency -- we study the parallel…