6 Search Results for "Cruciani, Emilio"

Document
DOI: 10.4230/LIPIcs.FUN.2026.14
The Careless Coupon Collector’s Problem

Authors: Emilio Cruciani and Aditi Dudeja

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We initiate the study of the Careless Coupon Collector’s Problem (CCCP), a novel variation of the classical coupon collector, that we envision as a model for information systems such as web crawlers, dynamic caches, and fault-resilient networks. In CCCP, a collector attempts to gather n distinct coupon types by obtaining one coupon type uniformly at random in each discrete round, however the collector is careless: at the end of each round, each collected coupon type is independently lost with probability p. We analyze the number of rounds required to complete the collection as a function of n and p. In particular, we show that it transitions from Θ(n ln n) when p = o((ln n)/n²) up to Θ(((np)/(1-p))ⁿ) when p = ω(1/n) in multiple distinct phases. Interestingly, when p = c/n, the process remains in a metastable phase, where the fraction of collected coupon types is concentrated around 1/(1+c) with probability 1-o(1), for a time window of length e^{Θ(n)}. Finally, we give an algorithm that computes the expected completion time of CCCP in O(n²) time.
Cite as

Emilio Cruciani and Aditi Dudeja. The Careless Coupon Collector’s Problem. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.FUN.2026.14,
  author =	{Cruciani, Emilio and Dudeja, Aditi},
  title =	{{The Careless Coupon Collector’s Problem}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.14},
  URN =		{urn:nbn:de:0030-drops-257333},
  doi =		{10.4230/LIPIcs.FUN.2026.14},
  annote =	{Keywords: Coupon Collector, Markov Chains, Metastability}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.26
Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders

Authors: Emilio Cruciani, Sebastian Forster, and Tijn de Vos

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study a multi-call variant of the classic PUSH&PULL rumor spreading process where nodes can contact k of their neighbors instead of a single one during both PUSH and PULL operations. We show that rumor spreading can be made faster at the cost of an increased amount of communication between the nodes. As a motivating example, consider the process on a complete graph of n nodes: while the standard PUSH&PULL protocol takes Θ(log n) rounds, we prove that our k-PUSH&PULL variant completes in Θ(log_{k} n) rounds, with high probability. We generalize this result in an expansion-sensitive way, as has been done for the classic PUSH&PULL protocol for different notions of expansion, e.g., conductance and vertex expansion. We consider small-set vertex expanders, graphs in which every sufficiently small subset of nodes has a large neighborhood, ensuring strong local connectivity. In particular, when the expansion parameter satisfies ϕ > 1, these graphs have a diameter of o(log n), as opposed to other standard notions of expansion. Since the graph’s diameter is a lower bound on the number of rounds required for rumor spreading, this makes small-set expanders particularly well-suited for fast information dissemination. We prove that k-PUSH&PULL takes O(log_{ϕ} n ⋅ log_{k} n) rounds in these expanders, with high probability. We complement this with a simple lower bound of Ω(log_{ϕ} n+ log_{k} n) rounds.
Cite as

Emilio Cruciani, Sebastian Forster, and Tijn de Vos. Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 26:1-26:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.DISC.2025.26,
  author =	{Cruciani, Emilio and Forster, Sebastian and de Vos, Tijn},
  title =	{{Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{26:1--26:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.26},
  URN =		{urn:nbn:de:0030-drops-248434},
  doi =		{10.4230/LIPIcs.DISC.2025.26},
  annote =	{Keywords: small set expansion, vertex expansion, rumor spreading, multi-call rumor spreading, push\&pull protocol}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.27
On the h-Majority Dynamics with Many Opinions

Authors: Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We present the first upper bound on the convergence time to consensus of the well-known h-majority dynamics with k opinions, in the synchronous setting, for h and k that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by x nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is ω(√x) and the initial plurality opinion is supported by at least x = ω(log n) nodes, then the process converges to plurality consensus in O(log n) rounds whenever h = ω(n log n / x). A main corollary is the following: if k = o(n / log n) and the process starts from an almost-balanced configuration with an initial bias of magnitude ω(√{n/k}) towards the initial plurality opinion, then any function h = ω(k log n) suffices to guarantee convergence to consensus in O(log n) rounds, with high probability. Our upper bound shows that the lower bound of Ω(k / h²) rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than Ω̃(k / h). Moreover, the bias we require is asymptotically smaller than the Ω(√{nlog n}) bias that guarantees plurality consensus in the 3-majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in ω(√x) for any value of k ≥ 2.
Cite as

Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale. On the h-Majority Dynamics with Many Opinions. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{damore_et_al:LIPIcs.DISC.2025.27,
  author =	{d'Amore, Francesco and D'Archivio, Niccol\`{o} and Giakkoupis, George and Natale, Emanuele},
  title =	{{On the h-Majority Dynamics with Many Opinions}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{27:1--27:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.27},
  URN =		{urn:nbn:de:0030-drops-248448},
  doi =		{10.4230/LIPIcs.DISC.2025.27},
  annote =	{Keywords: Distributed Algorithms, Randomized Algorithms, Markov Chains, Consensus Problem, Opinion dynamics, Plurality Consensus}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.69
Approximation Algorithms for Optimal Hopsets

Authors: Michael Dinitz, Ama Koranteng, and Yasamin Nazari

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
For a given graph G, a hopset H with hopbound β and stretch α is a set of edges such that between every pair of vertices u and v, there is a path with at most β hops in G ∪ H that approximates the distance between u and v up to a multiplicative stretch of α. Hopsets have found a wide range of applications for distance-based problems in various computational models since the 90s. More recently, there has been significant interest in understanding these fundamental objects from an existential and structural perspective. But all of this work takes a worst-case (or existential) point of view: How many edges do we need to add to satisfy a given hopbound and stretch requirement for any input graph? We initiate the study of the natural optimization variant of this problem: given a specific graph instance, what is the minimum number of edges that satisfy the hopbound and stretch requirements? We give approximation algorithms for a generalized hopset problem which, when combined with known existential bounds, lead to different approximation guarantees for various regimes depending on hopbound, stretch, and directed vs. undirected inputs. We complement our upper bounds with a lower bound that implies Label Cover hardness for directed hopsets and shortcut sets with hopbound at least 3.
Cite as

Michael Dinitz, Ama Koranteng, and Yasamin Nazari. Approximation Algorithms for Optimal Hopsets. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.ICALP.2025.69,
  author =	{Dinitz, Michael and Koranteng, Ama and Nazari, Yasamin},
  title =	{{Approximation Algorithms for Optimal Hopsets}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{69:1--69:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.69},
  URN =		{urn:nbn:de:0030-drops-234464},
  doi =		{10.4230/LIPIcs.ICALP.2025.69},
  annote =	{Keywords: Hopsets, Approximation Algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.42
Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model

Authors: Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We analyze the binary-state (either ℛ or ℬ) k-majority dynamics in a biased communication model where nodes have some fixed probability p, independent of the dynamics, of being seen in state ℬ by their neighbors. In this setting we study how p, as well as the initial unbalance between the two states, impact on the speed of convergence of the process, identifying sharp phase transitions.
Cite as

Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.DISC.2020.42,
  author =	{Cruciani, Emilio and Mimun, Hlafo Alfie and Quattropani, Matteo and Rizzo, Sara},
  title =	{{Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.42},
  URN =		{urn:nbn:de:0030-drops-131200},
  doi =		{10.4230/LIPIcs.DISC.2020.42},
  annote =	{Keywords: Biased Communication, Consensus, Majority Dynamics, Markov Chains, Metastability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.20
Step-By-Step Community Detection in Volume-Regular Graphs

Authors: Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k "stepwise" eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k eigenvalues and the gap between the k-th and the (k+1)-th eigenvalues is sufficiently large, the Averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.
Cite as

Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Step-By-Step Community Detection in Volume-Regular Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.ISAAC.2019.20,
  author =	{Becchetti, Luca and Cruciani, Emilio and Pasquale, Francesco and Rizzo, Sara},
  title =	{{Step-By-Step Community Detection in Volume-Regular Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.20},
  URN =		{urn:nbn:de:0030-drops-115163},
  doi =		{10.4230/LIPIcs.ISAAC.2019.20},
  annote =	{Keywords: Community detection, Distributed algorithms, Dynamics, Markov chains, Spectral analysis}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2020
  • 1 2019

  • Refine by Author
  • 4 Cruciani, Emilio
  • 2 Rizzo, Sara
  • 1 Becchetti, Luca
  • 1 D'Archivio, Niccolò
  • 1 Dinitz, Michael
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Distributed algorithms
  • 3 Mathematics of computing → Probabilistic algorithms
  • 2 Mathematics of computing → Markov processes
  • 1 Applied computing → Systems biology
  • 1 Mathematics of computing
  • Show More...

  • Refine by Keyword
  • 3 Markov Chains
  • 2 Metastability
  • 1 Approximation Algorithms
  • 1 Biased Communication
  • 1 Community detection
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact