ECCC-Report TR22-174https://eccc.weizmann.ac.il/report/2022/174Comments and Revisions published for TR22-174en-usFri, 16 Dec 2022 02:00:30 +0200
Revision 2
| Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds |
Raghuvansh Saxena,
Gillat Kol,
Klim Efremenko,
Dmitry Paramonov
https://eccc.weizmann.ac.il/report/2022/174#revision2Much 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 $\Omega(\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 $\Omega(\log n)$. We mention that the $\Omega(\log n)$ overhead in both our results is tight. Fri, 16 Dec 2022 02:00:30 +0200https://eccc.weizmann.ac.il/report/2022/174#revision2
Revision 1
| Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds |
Raghuvansh Saxena,
Gillat Kol,
Klim Efremenko,
Dmitry Paramonov
https://eccc.weizmann.ac.il/report/2022/174#revision1Much 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 $\Omega(\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 $\Omega(\log n)$. We mention that the $\Omega(\log n)$ overhead in both our results is tight. Tue, 06 Dec 2022 16:26:24 +0200https://eccc.weizmann.ac.il/report/2022/174#revision1
Paper TR22-174
| Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds |
Raghuvansh Saxena,
Gillat Kol,
Klim Efremenko,
Dmitry Paramonov
https://eccc.weizmann.ac.il/report/2022/174Much 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 $\Omega(\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 $\Omega(\log n)$. We mention that the $\Omega(\log n)$ overhead in both our results is tight. Sun, 04 Dec 2022 06:13:34 +0200https://eccc.weizmann.ac.il/report/2022/174