Simulating noisy channel interaction [extended abstract]

Mark Braverman, Jieming Mao

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

3 Scopus citations

Abstract

We show that T rounds of interaction over the binary symmetric channel BSC1=2-ε with feedback can be simulated with O(ε2T) rounds of interaction over a noiseless channel. We also introduce a more general "energy cost" model of interaction over a noisy channel. We show energy cost to be equivalent to external information complexity, which implies that our simulation results are unlikely to carry over to energy complexity. Our main technical innovation is a self-reduction from simulating a noisy channel to simulating a slightly-less-noisy channel, which may have other applications in the area of interactive compression.

Original languageEnglish (US)
Title of host publicationITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery, Inc
Pages21-30
Number of pages10
ISBN (Electronic)9781450333337
DOIs
StatePublished - Jan 11 2015
Event6th Conference on Innovations in Theoretical Computer Science, ITCS 2015 - Rehovot, Israel
Duration: Jan 11 2015Jan 13 2015

Publication series

NameITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science

Other

Other6th Conference on Innovations in Theoretical Computer Science, ITCS 2015
CountryIsrael
CityRehovot
Period1/11/151/13/15

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Keywords

  • Communication complexity
  • Information complexity
  • Noisy channel

Fingerprint Dive into the research topics of 'Simulating noisy channel interaction [extended abstract]'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Mao, J. (2015). Simulating noisy channel interaction [extended abstract]. In ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science (pp. 21-30). (ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science). Association for Computing Machinery, Inc. https://doi.org/10.1145/2688073.2688087