43 citations · 116 across the 21 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
cs.DC2018
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…
cs.DC2018
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,…