43 citations · 96 across the 19 of their papers we have counts for
29 papers
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…
Parallel Load Balancing on Constrained Client-Server Topologies
Andrea Clementi, Emanuele Natale, Isabella Ziccardi
We study parallel \emph{Load Balancing} protocols for a client-server distributed model defined as follows. There is a set $\sC$ of clients and a set $\sS$ of servers where…
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…
A Comparative Study of Neural Network Compression
Hossein Baktash, Emanuele Natale, Laurent Viennot
There has recently been an increasing desire to evaluate neural networks locally on computationally-limited devices in order to exploit their recent effectiveness for several appli…
On the Necessary Memory to Compute the Plurality in Multi-Agent Systems
Emanuele Natale, Iliad Ramezani
We consider the Relative-Majority Problem (also known as Plurality), in which, given a multi-agent system where each agent is initially provided an input value out of a set of …
Finding a Bounded-Degree Expander Inside a Dense One
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if is a -regular dense expander then there is an edge-induced subgraph $H=(V…
Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise
Andrea Clementi, Luciano Gualà, Emanuele Natale +3
Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast,…
Distributed Community Detection via Metastability of the 2-Choices Dynamics
Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca
We investigate the behavior of a simple majority dynamics on networks of agents whose interaction topology exhibits a community structure. By leveraging recent advancements in the…
Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation
Luca Becchetti, Vincenzo Bonifaci, Emanuele Natale
The computation of electrical flows is a crucial primitive for many recently proposed optimization algorithms on weighted networks. While typically implemented as a centralized sub…
Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks
Emilio Cruciani, Emanuele Natale, André Nusser +1
Consider the following process on a network: Each agent initially holds either opinion blue or red; then, in each round, each agent looks at two random neighbors and, if the two ha…
Limits for Rumor Spreading in stochastic populations
Lucas Boczkowski, Ofer Feinerman, Amos Korman +1
Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate…
Average whenever you meet: Opportunistic protocols for community detection
Luca Becchetti, Andrea Clementi, Pasin Manurangsi +4
Consider the following asynchronous, opportunistic communication model over a graph : in each round, one edge is activated uniformly and independently at random and (only) its t…
Ignore or Comply? On Breaking Symmetry in Consensus
Petra Berenbrink, Andrea Clementi, Robert Elsässer +3
We study consensus processes on the complete graph of nodes. Initially, each node supports one from up to n opinions. Nodes randomly and in parallel sample the opinions of cons…
KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
Michele Borassi, Emanuele Natale
We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world c…
Large Peg-Army Maneuvers
Luciano Gualà, Stefano Leucci, Emanuele Natale +1
Despite its long history, the classical game of peg solitaire continues to attract the attention of the scientific community. In this paper, we consider two problems with an algori…
Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits
Lucas Boczkowski, Amos Korman, Emanuele Natale
This paper considers the basic model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify…
Find Your Place: Simple Distributed Algorithms for Community Detection
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
Given an underlying graph, we consider the following \emph{dynamics}: Initially, each node locally chooses a value in , uniformly at random and independently of other nod…
Stabilizing Consensus with Many Opinions
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
We consider the following distributed consensus problem: Each node in a complete communication network of size initially holds an \emph{opinion}, which is chosen arbitrarily fr…
On the Voting Time of the Deterministic Majority Process
Dominik Kaaser, Frederik Mallmann-Trenn, Emanuele Natale
In the deterministic binary majority process we are given a simple graph where each node has one out of two initial opinions. In every round, every node adopts the majority opinion…
Probabilistic Self-Stabilization
Luca Becchetti, Andrea Clementi, Emanuele Natale +1
By using concrete scenarios, we present and discuss a new concept of probabilistic Self-Stabilization in Distributed Systems.
Noisy Rumor Spreading and Plurality Consensus
Pierre Fraigniaud, Emanuele Natale
Error-correcting codes are efficient methods for handling \emph{noisy} communication channels in the context of technological networks. However, such elaborate methods differ a lot…