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
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.
Francesco d’Amore, Andrea Clementi, and Emanuele Natale
Springer Science and Business Media LLC
Francesco d’Amore and Isabella Ziccardi
Springer International Publishing
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 ℓ.
Francesco d’Amore, Andrea Clementi, and Emanuele Natale
Springer International Publishing