2026-07-23T20:15:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17549 2024-03-06T10:59:53Z ddc:004 open_access

Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds Efremenko, Klim Kol, Gillat Paramonov, Dmitry Saxena, Raghuvansh R. Beeping Model Radio Networks Much of today’s communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric f-channels: In every round of the f-channel, each of its n parties decides to either broadcast or not, and the channel outputs f(m), where m is the number of broadcasting parties. Our first result is that the well studied beeping channel, where f is the threshold-1 function, is not stronger than any other f-channel. To this end, we design a protocol over the f-channel and prove that any protocol that simulates it over the beeping channel blows up the round complexity by a factor of Ω(log n). Our lower bound technique may be of independent interest, as it essentially generalizes the popular fooling set technique by exploiting a "local" relaxation of combinatorial rectangles. Curiously, while this result shows the limitations of a noiseless channel, namely, the beeping channel, we are able to use it to show the limitations of the noisy version of many other channels. This includes the extensively studied single-hop radio network model with collisions-as-silence (CAS), which is equivalent to the f-channel with f(m) = 1 iff m = 1. In particular, our second and main result, obtained from the first, shows that converting CAS protocols to noise resilient ones may incur a large performance overhead, i.e., no constant rate interactive code exists. To this end, we design a CAS protocol and prove that any protocol that simulates it over the noisy CAS model with correlated stochastic noise, blows up the round complexity by a factor of Ω(log n). We mention that the Ω(log n) overhead in both our results is tight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klim Efremenko and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.46 urn:nbn:de:0030-drops-175499 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.46 eng https://creativecommons.org/licenses/by/4.0/legalcode