Francesco d'Amore

@unibocconi.eu

Department of Computing Sciences
Bocconi University

2022-2023: postdoc at Aalto University, (Espoo, Finland) In prof. Jukka Suomela's team
2023-ongoing: postdoc at Bocconi University (Milan, Italy) in prof. Luca Trevisan's team.

EDUCATION

2013-2019 B.Sc. and M.Sc. in Mathematics at University of Rome "La Sapienza" (Rome, Italy).
2019-2022 P.h.D. in Computer Science at Inria Sophia Antipolis & Université Côte d'Azur (Sophia Antipolis, France).

RESEARCH, TEACHING, or OTHER INTERESTS

Theoretical Computer Science, Computational Theory and Mathematics, Computer Networks and Communications, Discrete Mathematics and Combinatorics

Scopus Publications

Scholar Citations

Scholar h-index

Scholar i10-index

Scopus Publications

Phase transition of the 3-majority opinion dynamics with noisy interactions
Francesco d'Amore and Isabella Ziccardi
Elsevier BV

No Distributed Quantum Advantage for Approximate Graph Coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela
ACM
We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: We give a new distributed algorithm that finds a c-coloring in χ-chromatic graphs in Õ(n1/α) rounds, with α = ⌊c−1/χ − 1⌋. We prove that any distributed algorithm for this problem requires Ω(n1/α) rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.

Brief Announcement: Distributed Derandomization Revisited

Revisiting the Random Subset Sum Problem
A. D. Cunha, Francesco d’Amore, F. Giroire, Hicham Lesfari, Emanuele Natale and L. Viennot

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 $z$, random variables $X_1, \\ldots, X_n$, and an error parameter $\\varepsilon>0$, and we seek a subset of the $X_i$s whose sum approximates $z$ up to error $\\varepsilon$. In this setup, it has been shown that, under mild assumptions on the distribution of the random variables, a sample of size $\\mathcal{O}(\\log(1/\\varepsilon))$ suffices to obtain, with high probability, approximations for all values in $[-1/2, 1/2]$. Recently, this result has been rediscovered outside the algorithms community, enabling meaningful progress in other fields. In this work we present an alternative proof for this theorem, with a more direct approach and resourcing to more elementary tools.

Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets

Phase transition of a nonlinear opinion dynamics with noisy interactions
Francesco d’Amore, Andrea Clementi, and Emanuele Natale
Springer Science and Business Media LLC

Planning with Biological Neurons and Synapses

Phase Transition of the 3-Majority Dynamics with Uniform Communication Noise
Francesco d’Amore and Isabella Ziccardi
Springer International Publishing

Search via Parallel Lévy Walks on Z2
Andrea Clementi, Francesco d'Amore, George Giakkoupis, and Emanuele Natale
ACM
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 hitting time of Lévy walks on the infinite two-dimensional grid. We consider k independent discrete-time Lévy walks, with the same exponent α ∈(1,∞), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance ℓ. % We show that for any choice of k and ℓ from a large range, there is a unique optimal exponent α_k,∈ (2,3), for which the hitting time is Õ(ℓ2/k) w.h.p., while modifying the exponent by any constant term ε>0 increases the hitting time by a factor polynomial in ℓ, or the walks fail to hit the target almost surely. % Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and ℓ are unknown: The exponent of each Lévy walk is just chosen independently and uniformly at random from the interval (2,3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). % Our results should be contrasted with a line of previous work showing that the exponent α = 2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and ℓ, and that randomizing the choice of the exponents works simultaneously for all k and ℓ.

Phase transition of a non-linear opinion dynamics with noisy interactions: (Extended abstract)
Francesco d’Amore, Andrea Clementi, and Emanuele Natale
Springer International Publishing

RECENT SCHOLAR PUBLICATIONS

Distributed Quantum Advantage for Local Problems
A Balliu, S Brandt, X Coiteux-Roy, F d'Amore, M Equi, FL Gall, H Lievonen, ...
arXiv preprint arXiv:2411.03240 2024

No distributed quantum advantage for approximate graph coloring
X Coiteux-Roy, F d'Amore, R Gajjala, F Kuhn, F Le Gall, H Lievonen, ...
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 1901-1910 2024

Online locality meets distributed quantum computing
A Akbari, X Coiteux-Roy, F d'Amore, FL Gall, H Lievonen, D Melnyk, ...
arXiv preprint arXiv:2403.01903 2024

Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets
A da Cunha, F d'Amore, E Natale
Advances in Neural Information Processing Systems 36 2024

Revisiting the Random Subset Sum Problem
ACW da Cunha, F d'Amore, F Giroire, H Lesfari, E Natale, L Viennot
31st Annual European Symposium on Algorithms (ESA 2023) 274, 37:1--37:11 2023

Brief announcement: Distributed derandomization revisited
S Dahal, F d'Amore, H Lievonen, T Picavet, J Suomela
37th International Symposium on Distributed Computing (DISC 2023), 40: 1-40: 5 2023

Phase transition of a nonlinear opinion dynamics with noisy interactions
F d’Amore, A Clementi, E Natale
Swarm Intelligence 16 (4), 261-304 2022

On the collective behaviors of bio-inspired distributed systems
F d'Amore
Universit Cte d'Azur 2022

On the multidimensional random subset sum problem
L Becchetti, ACW da Cunha, A Clementi, F d'Amore, H Lesfari, E Natale, ...
arXiv preprint arXiv:2207.13944 2022

Planning with biological neurons and synapses
F d'Amore, D Mitropolsky, P Crescenzi, E Natale, CH Papadimitriou
Proceedings of the AAAI Conference on Artificial Intelligence 36 (1), 21-28 2022

Phase transition of the 3-majority dynamics with uniform communication noise
F d’Amore, I Ziccardi
International Colloquium on Structural Information and Communication 2022

Search via Parallel Lvy Walks on Z^2
A Clementi, F d'Amore, G Giakkoupis, E Natale
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing 2021

On some Opinion Dynamics in Multi-Agent Systems
E Cruciani, F d'Amore, E Natale
MOMI2021: Le Monde des Mathematiques Industrielles 2021

MOST CITED SCHOLAR PUBLICATIONS

Phase transition of a nonlinear opinion dynamics with noisy interactions
F d’Amore, A Clementi, E Natale
Swarm Intelligence 16 (4), 261-304 2022
Citations: 16

Search via Parallel Lvy Walks on Z^2
A Clementi, F d'Amore, G Giakkoupis, E Natale
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing 2021
Citations: 16

Online locality meets distributed quantum computing
A Akbari, X Coiteux-Roy, F d'Amore, FL Gall, H Lievonen, D Melnyk, ...
arXiv preprint arXiv:2403.01903 2024
Citations: 10

Phase transition of the 3-majority dynamics with uniform communication noise
F d’Amore, I Ziccardi
International Colloquium on Structural Information and Communication 2022
Citations: 9

Revisiting the Random Subset Sum Problem
ACW da Cunha, F d'Amore, F Giroire, H Lesfari, E Natale, L Viennot
31st Annual European Symposium on Algorithms (ESA 2023) 274, 37:1--37:11 2023
Citations: 8

Planning with biological neurons and synapses
F d'Amore, D Mitropolsky, P Crescenzi, E Natale, CH Papadimitriou
Proceedings of the AAAI Conference on Artificial Intelligence 36 (1), 21-28 2022
Citations: 8

On the multidimensional random subset sum problem
L Becchetti, ACW da Cunha, A Clementi, F d'Amore, H Lesfari, E Natale, ...
arXiv preprint arXiv:2207.13944 2022
Citations: 5

Distributed Quantum Advantage for Local Problems
A Balliu, S Brandt, X Coiteux-Roy, F d'Amore, M Equi, FL Gall, H Lievonen, ...
arXiv preprint arXiv:2411.03240 2024
Citations: 3

Brief announcement: Distributed derandomization revisited
S Dahal, F d'Amore, H Lievonen, T Picavet, J Suomela
37th International Symposium on Distributed Computing (DISC 2023), 40: 1-40: 5 2023
Citations: 3