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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Multiparty interactive coding allows a network of <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC 1994) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of <inline-formula> <tex-math notation="LaTeX">$O(\log (\Delta +1))$ </tex-math></inline-formula> for networks whose topology has a maximal degree <inline-formula> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula>. Vitally, the communication model in their work forces all the parties to send one message at every round of the protocol, even if they have nothing to send. We re-examine the question of multiparty interactive coding, lifting the requirement that forces all the parties to communicate at each and every round. We use the recently developed information-theoretic machinery of Braverman <italic>et al.</italic> (J. ACM 2018) to show that if the network’s topology is a cycle, then there is a specific cycle task for which any coding scheme has a communication blowup of <inline-formula> <tex-math notation="LaTeX">$\Omega (\log n)$ </tex-math></inline-formula>. This is quite surprising since the cycle has a maximal degree of <inline-formula> <tex-math notation="LaTeX">$\Delta =2$ </tex-math></inline-formula>, implying a coding with a <italic>constant blowup</italic> when all parties are forced to speak at all rounds. We complement our lower bound with a matching coding scheme for the cycle task that has a communication blowup of <inline-formula> <tex-math notation="LaTeX">$\Theta (\log n)$ </tex-math></inline-formula>. This makes our lower bound for the cycle task tight.

Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks