Radio network coding requires logarithmic overhead

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, meaning that it was the only neighbor broadcasting. While the (noiseless) radio network model received a lot of attention over the last few decades, the effect of noise on radio networks is still not well understood. In this paper, we take a step forward and show that making radio network protocols resilient to noise may require a substantial performance overhead. Specifically, we construct a multi-hop network and a communication protocol over this network that works in T rounds when there is no noise. We prove that any scheme that simulates our protocol and is resilient to stochastic noise, requires at least cT log(n) rounds, for some constant c. This stands in contrast to our previous result (STOC, 2018), showing that protocols over the single-hop (clique) network can be made noise resilient with only a constant overhead. Our result also settles a recent conjecture by Censor-Hillel, Haeupler, Hershkowitz, Zuzic (2018). We complement the above result by giving a scheme to simulate any protocol with a fixed order of transmissions with only an O(log (n)) overhead.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Number of pages22
ISBN (Electronic)9781728149523
StatePublished - Nov 2019
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • Communication Complexity
  • Interactive Coding
  • Lower Bounds
  • Wireless Broadcast


Dive into the research topics of 'Radio network coding requires logarithmic overhead'. Together they form a unique fingerprint.

Cite this