Optimal channel utilization with limited feedback

Gianluca De Marco, Tomasz Jurdziński, Dariusz R. Kowalski

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


A channel with multiplicity feedback in case of collision returns the exact number of stations simultaneously transmitting. In this model, Θ((dlog⁡(n/d))/log⁡d) time rounds are sufficient and necessary to identify d transmitting stations out of n. In contrast, in the ternary feedback model the time complexity is Θ(dlog⁡(n/d)). Generalizing, we can define a feedback interval [x,y], where 0≤x≤y≤d, such that the channel returns the exact number of transmitting stations only if this number is within that interval. For a feedback interval centered in d/2 we show that it is possible to get the same optimal time complexity for the channel with multiplicity feedback even if the interval has only size O(dlog⁡d). On the other hand, if we further reduce the size to [Figure presented], then we show that no protocol having time complexity Θ((dlog⁡(n/d))/(log⁡d)) is possible.

Original languageEnglish (US)
Pages (from-to)21-33
Number of pages13
JournalJournal of Computer and System Sciences
StatePublished - Aug 2021


  • Algorithm
  • Distributed
  • Group testing
  • Limited feedback
  • Lower bound
  • Multiple-access channel
  • Threshold group testing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Optimal channel utilization with limited feedback'. Together they form a unique fingerprint.

Cite this