English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the fundamental problem of reliable interactive communication over anoisy channel. In a breakthrough sequence of papers published in 1992 and 1993,Schulman gave non-constructive proofs of the existence of general methods toemulate any two-party interactive protocol such that: (1) the emulationprotocol takes a constant-factor longer than the original protocol, and (2) ifthe emulation protocol is executed over a noisy channel, then the probabilitythat the emulation protocol fails is exponentially small in the total length ofthe protocol. Unfortunately, Schulman's emulation procedures either only workin a model with a large amount of shared randomness, or are non-constructive inthat they rely on the existence of good tree codes. The only known proofs ofthe existence of good tree codes are non-constructive, and finding an explicitconstruction remains an important open problem. Indeed, randomly generated treecodes are not good tree codes with overwhelming probability.  In this work, we revisit the problem of reliable interactive communication,and obtain the following results: We introduce a new notion of goodness for atree code, and define the notion of a potent tree code. We believe that thisnotion is of independent interest. We prove the correctness of an explicitemulation procedure based on any potent tree code. We show that a randomlygenerated tree code (with suitable constant alphabet size) is a potent treecode with overwhelming probability. Furthermore we are able to partiallyderandomize this result using only O(n) random bits, where $n$ is the depth ofthe tree.  These results allow us to obtain the first fully explicit emulation procedurefor reliable interactive communication over noisy channels with a constantcommunication overhead, and exponentially small failure probability.

Potent Tree Codes and their applications: Coding for Interactive Communication, revisited