2022-2023: postdoc at Aalto University, (Espoo, Finland) In prof. Jukka Suomela's team
2023-2025: postdoc at Bocconi University (Milan, Italy) in prof. Luca Trevisan's team
2025-ongoing: international postodctoral researchet at Gran Sasso Science Institute (L'Aquila, Italy).
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
Online Locality Meets Distributed Quantum Computing Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, et al. Proceedings of the Annual ACM Symposium on Theory of Computing, 2025 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-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: (1) All LCL problems solvable with locality O(log⋆n) in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality O(1). This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. (2) In rooted trees, if we can solve an LCL problem with locality o(logloglogn) in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality O(log⋆n) in the classical deterministic LOCAL model. One of many implications is that in rooted trees, O(log⋆n) locality in quantum-LOCAL is not stronger than O(log⋆n) locality in classical LOCAL.
Distributed Quantum Advantage for Local Problems Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, et al. Proceedings of the Annual ACM Symposium on Theory of Computing, 2025 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 prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree Δ, any classical (deterministic or randomized) LOCAL model algorithm will require Ω(Δ) rounds to solve the iterated GHZ problem, while the problem can be solved in 1 round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires Ω(Δ) rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.
No Distributed Quantum Advantage for Approximate Graph Coloring Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, et al. Proceedings of the Annual ACM Symposium on Theory of Computing, 2024 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.
Revisiting the Random Subset Sum Problem A. D. Cunha, Francesco d’Amore, F. Giroire, Hicham Lesfari, Emanuele Natale, et al. Leibniz International Proceedings in Informatics Lipics, 2023 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 Advances in Neural Information Processing Systems, 2023
Planning with Biological Neurons and Synapses Francesco D'Amore, Daniel Mitropolsky, Pierluigi Crescenzi, Emanuele Natale, Christos H. Papadimitriou Proceedings of the 36th Aaai Conference on Artificial Intelligence Aaai 2022, 2022
Search via Parallel Lévy Walks on Z2 Andrea Clementi, Francesco d'Amore, George Giakkoupis, Emanuele Natale Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 2021
Brief Announcement: DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus F d'Amore, ND Archivio, G Giakkoupis, F Giroire, E Natale PODC 2026-ACM Symposium on Principles of Distributed Computing , 2026 2026
DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus F d'Amore, N d'Archivio, G Giakkoupis, F Giroire, E Natale arXiv preprint arXiv:2604.03648 , 2026 2026 Citations: 1
Survival in infants with trisomy 18, palliative care and ethical reflections: a single center considerations S Caggiano, S Persia, F D’Amore, M Macchiaiolo, M Fornari, V Clemente, ... Italian Journal of Pediatrics , 2026 2026
Distributed quantum advantage in locally checkable labeling problems A Balliu, F Casagrande, F d’Amore, M Equi, B Keller, H Lievonen, ... Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms … , 2026 2026 Citations: 6
New Hardness Results for the LOCAL Model via a Simple Self-Reduction A Balliu, F Casagrande, F d'Amore, D Olivetti arXiv preprint arXiv:2510.19972 , 2025 2025
Distributed Algorithms for Potential Problems A Balliu, T Boudier, F d'Amore, F Kuhn, D Olivetti, G Schmid, J Suomela arXiv preprint arXiv:2507.12038 , 2025 2025
On the -majority dynamics with many opinions F d'Amore, N d'Archivio, G Giakkoupis, E Natale arXiv preprint arXiv:2506.20218 , 2025 2025 Citations: 4
Distributed quantum advantage for local problems A Balliu, S Brandt, X Coiteux-Roy, F d'Amore, M Equi, F Le Gall, ... Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 451-462 , 2025 2025 Citations: 22
Online locality meets distributed quantum computing A Akbari, X Coiteux-Roy, F d'Amore, F Le Gall, H Lievonen, D Melnyk, ... Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 1295-1306 , 2025 2025 Citations: 34
New limits on distributed quantum advantage: Dequantizing linear programs A Balliu, C Coupette, A Cruciani, F d'Amore, M Equi, H Lievonen, ... arXiv preprint arXiv:2506.07574 , 2025 2025 Citations: 6
On the limits of distributed quantum computing F d'Amore arXiv preprint arXiv:2503.11394 , 2025 2025 Citations: 3
Phase transition of the 3-majority opinion dynamics with noisy interactions F d'Amore, I Ziccardi Theoretical Computer Science 1028, 115030 , 2025 2025 Citations: 4
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 2024 Citations: 36
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 2024 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 2023 Citations: 7
Distributed derandomization revisited S Dahal, F d'Amore, H Lievonen, T Picavet, J Suomela arXiv preprint arXiv:2305.07351 , 2023 2023 Citations: 8
On the collective behaviors of bio-inspired distributed systems F d'Amore Université Côte d'Azur , 2022 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 2022 Citations: 5
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 2022 Citations: 12
Phase transition of the 3-majority dynamics with uniform communication noise F d’Amore, I Ziccardi International Colloquium on Structural Information and Communication … , 2022 2022 Citations: 14
MOST CITED SCHOLAR PUBLICATIONS
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 2024 Citations: 36
Online locality meets distributed quantum computing A Akbari, X Coiteux-Roy, F d'Amore, F Le Gall, H Lievonen, D Melnyk, ... Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 1295-1306 , 2025 2025 Citations: 34
Phase transition of a non-linear opinion dynamics with noisy interactions F d’Amore, A Clementi, E Natale International Colloquium on Structural Information and Communication … , 2020 2020 Citations: 26
Search via Parallel Lévy 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 2021 Citations: 23
Distributed quantum advantage for local problems A Balliu, S Brandt, X Coiteux-Roy, F d'Amore, M Equi, F Le Gall, ... Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 451-462 , 2025 2025 Citations: 22
Phase transition of the 3-majority dynamics with uniform communication noise F d’Amore, I Ziccardi International Colloquium on Structural Information and Communication … , 2022 2022 Citations: 14
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 2022 Citations: 12
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 2024 Citations: 9
Distributed derandomization revisited S Dahal, F d'Amore, H Lievonen, T Picavet, J Suomela arXiv preprint arXiv:2305.07351 , 2023 2023 Citations: 8
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 2023 Citations: 7
Distributed quantum advantage in locally checkable labeling problems A Balliu, F Casagrande, F d’Amore, M Equi, B Keller, H Lievonen, ... Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms … , 2026 2026 Citations: 6
New limits on distributed quantum advantage: Dequantizing linear programs A Balliu, C Coupette, A Cruciani, F d'Amore, M Equi, H Lievonen, ... arXiv preprint arXiv:2506.07574 , 2025 2025 Citations: 6
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 2022 Citations: 5
On the -majority dynamics with many opinions F d'Amore, N d'Archivio, G Giakkoupis, E Natale arXiv preprint arXiv:2506.20218 , 2025 2025 Citations: 4
Phase transition of the 3-majority opinion dynamics with noisy interactions F d'Amore, I Ziccardi Theoretical Computer Science 1028, 115030 , 2025 2025 Citations: 4
On the limits of distributed quantum computing F d'Amore arXiv preprint arXiv:2503.11394 , 2025 2025 Citations: 3
DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus F d'Amore, N d'Archivio, G Giakkoupis, F Giroire, E Natale arXiv preprint arXiv:2604.03648 , 2026 2026 Citations: 1
Brief Announcement: DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus F d'Amore, ND Archivio, G Giakkoupis, F Giroire, E Natale PODC 2026-ACM Symposium on Principles of Distributed Computing , 2026 2026
Survival in infants with trisomy 18, palliative care and ethical reflections: a single center considerations S Caggiano, S Persia, F D’Amore, M Macchiaiolo, M Fornari, V Clemente, ... Italian Journal of Pediatrics , 2026 2026
New Hardness Results for the LOCAL Model via a Simple Self-Reduction A Balliu, F Casagrande, F d'Amore, D Olivetti arXiv preprint arXiv:2510.19972 , 2025 2025
