List and unique coding for interactive communication in the presence of adversarial noise

Mark Braverman, Klim Efremenko

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

30 Scopus citations

Abstract

In this paper we extend the notion of list-decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2-ε, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α Alice's communication and up to a fraction β of Bob's communication. We use list-decoding in order to fully characterize the region RU of pairs (α β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-differentiable curve with infinitely many pieces. We show that outside this region, the rate must be exponential. This suggests that in some error regimes, list-decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α β) for which one-sided unique decoding is possible in a way that Alice will output the correct answer.

Original languageEnglish (US)
Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PublisherIEEE Computer Society
Pages236-245
Number of pages10
ISBN (Electronic)9781479965175
DOIs
StatePublished - Dec 7 2014
Event55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States
Duration: Oct 18 2014Oct 21 2014

Publication series

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

Other

Other55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
CountryUnited States
CityPhiladelphia
Period10/18/1410/21/14

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Interactive Communication
  • List Decodable Codes
  • Tree Codes

Fingerprint Dive into the research topics of 'List and unique coding for interactive communication in the presence of adversarial noise'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Efremenko, K. (2014). List and unique coding for interactive communication in the presence of adversarial noise. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 236-245). [6979008] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). IEEE Computer Society. https://doi.org/10.1109/FOCS.2014.33