Author name cluster

Francesco d'Amore

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2025 Journal Article

Phase transition of the 3-majority opinion dynamics with noisy interactions

Francesco d'Amore
Isabella Ziccardi

Communication noise is a common feature in several real-world scenarios where systems of agents need to communicate in order to pursue some collective task. Indeed, many biologically inspired systems that try to achieve agreements on some opinion must implement resilient dynamics, i. e. that are not strongly affected by noisy communications. In this work, we study the 3-Majority dynamics, an opinion dynamics that has been shown to be an efficient protocol for the majority consensus problem, in which we introduce a simple feature of uniform communication noise, following D'Amore et al. (2022). We prove that, in the fully connected communication network of n agents and in the binary opinion case, the process induced by the 3-Majority dynamics exhibits a phase transition. For a noise probability p < 1 / 3, the dynamics reach in logarithmic time an almost-consensus metastable phase which lasts for a polynomial number of rounds with high probability. We characterize this phase by showing that there exists an attractive equilibrium value s eq ∈ [ n ] for the bias of the system, i. e. the difference between the majority community size and the minority one. Moreover, we show that the agreement opinion is the initial majority one if the bias towards it is of magnitude Ω ( n log ⁡ n ) in the initial configuration. If, instead, p > 1 / 3, we show that no form of consensus is possible, and any information regarding the initial majority opinion is lost in logarithmic time with high probability. Despite more communications per-round being allowed, the 3-Majority dynamics surprisingly turns out to be less resilient to noise than the Undecided-State dynamics, whose noise threshold value is p = 1 / 2.

Details DOI

NeurIPS Conference 2023 Conference Paper

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

Arthur da Cunha
Francesco d'Amore
Natale Natale

The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised neural networks likely contain subnetworks that perform well without any training. Although unstructured pruning has been extensively studied in this context, its structured counterpart, which can deliver significant computational and memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the limitations of the underlying mathematical tools used in formal analyses of the SLTH. In this paper, we overcome these limitations: we leverage recent advances in the multidimensional generalisation of the Random Subset-Sum Problem and obtain a variant that admits the stochastic dependencies that arise when addressing structured pruning in the SLTH. We apply this result to prove, for a wide class of random Convolutional Neural Networks, the existence of structured subnetworks that can approximate any sufficiently smaller network. This result provides the first sub-exponential bound around the SLTH for structured pruning, opening up new avenues for further research on the hypothesis and contributing to the understanding of the role of over-parameterization in deep learning.

PDF Details

AAAI Conference 2022 Conference Paper

Planning with Biological Neurons and Synapses

Francesco d'Amore
Daniel Mitropolsky
Pierluigi Crescenzi
Emanuele Natale
Christos H. Papadimitriou

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 it is carried out exclusively through the spiking of neurons. Even though much has been accomplished in the blocks world over the past five decades, we believe that this is the first algorithm of its kind. The input is a sequence of symbols encoding an initial set of block stacks as well as a target set, and the output is a sequence of motion commands such as “put the top block in stack 1 on the table”. The program is written in the Assembly Calculus, a recently proposed computational framework meant to model computation in the brain by bridging the gap between neural activity and cognitive function. Its elementary objects are assemblies of neurons (stable sets of neurons whose simultaneous firing signifies that the subject is thinking of an object, concept, word, etc.), its commands include project and merge, and its execution model is based on widely accepted tenets of neuroscience. A program in this framework essentially sets up a dynamical system of neurons and synapses that eventually, with high probability, accomplishes the task. The purpose of this work is to establish empirically that reasonably large programs in the Assembly Calculus can execute correctly and reliably; and that rather realistic — if idealized — higher cognitive functions, such as planning in the blocks world, can be implemented successfully by such programs.

PDF Details