{"ID":2878575,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.18017","arxiv_id":"2508.18017","title":"Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders","abstract":"We study a multi-call variant of the classic PUSH\u0026PULL 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\u0026PULL protocol takes $Θ(\\log n)$ rounds, we prove that our $k$-PUSH\u0026PULL 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\u0026PULL 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 $φ\u003e 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\u0026PULL takes $O(\\log_φ n \\cdot \\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.","short_abstract":"We study a multi-call variant of the classic PUSH\u0026PULL 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 motivati...","url_abs":"https://arxiv.org/abs/2508.18017","url_pdf":"https://arxiv.org/pdf/2508.18017v2","authors":"[\"Emilio Cruciani\",\"Sebastian Forster\",\"Tijn de Vos\"]","published":"2025-08-25T13:32:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}