## Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 |

Editors | Yael Tauman Kalai |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772631 |

DOIs | |

State | Published - Jan 1 2023 |

Event | 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 - Cambridge, United States Duration: Jan 10 2023 → Jan 13 2023 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 251 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 |
---|---|

Country/Territory | United States |

City | Cambridge |

Period | 1/10/23 → 1/13/23 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Beeping Model
- Radio Networks