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 coding schemes for error correction in interactive communications.Such interactive coding schemes simulate any $n$-round interactive protocolusing $N$ rounds over an adversarial channel that corrupts up to $\rho N$transmissions. Important performance measures for a coding scheme are itsmaximum tolerable error rate $\rho$, communication complexity $N$, andcomputational complexity.  We give the first coding scheme for the standard setting which performsoptimally in all three measures: Our randomized non-adaptive coding scheme hasa near-linear computational complexity and tolerates any error rate $\delta <1/4$ with a linear $N = \Theta(n)$ communication complexity. This improves overprior results which each performed well in two of these measures.  We also give results for other settings of interest, namely, the firstcomputationally and communication efficient schemes that tolerate $\rho <\frac{2}{7}$ adaptively, $\rho < \frac{1}{3}$ if only one party is required todecode, and $\rho < \frac{1}{2}$ if list decoding is allowed. These are theoptimal tolerable error rates for the respective settings. These coding schemesalso have near linear computational and communication complexity.  These results are obtained via two techniques: We give a general black-boxreduction which reduces unique decoding, in various settings, to list decoding.We also show how to boost the computational and communication efficiency of anylist decoder to become near linear.

Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding