Publications (51)
Simple Dynamics for Plurality Consensus
Luca Becchetti, Andrea Clementi, Emanuele Natale +3
We study a \emph{Plurality-Consensus} process in which each of anonymous agents of a communication network initially supports an opinion (a color chosen from a finite set …
Repurposing acquisition devices into trigger-based timing synchronization of breakdown events during MITICA high voltage holding experiments
Andrea Rigoni Garola, Luca Lotto, Gabriele Manduchi +8
A critical requirement for MITICA -- a full-scale prototype of the heating Neutral Beam Injectors hosted at the Consorzio RFX Neutral Beam Test Facility for the ITER experiment --…
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=(…
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…
Unique Games on the Hypercube
Naman Agarwal, Guy Kindler, Alexandra Kolla +1
In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instanc…
A Higher-Order Cheeger's Inequality
Shayan Oveis Gharan, Luca Trevisan
A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue 1 in the normalized adjacenc…