The Power of Shared Randomness in Uncertain Communication

DOI10.4230/LIPICS.ICALP.2017.49zbMATH Open1441.68049arXiv1705.01082MaRDI QIDQ5111380FDOQ5111380

Badih Ghazi, Madhu Sudan

Publication date: 27 May 2020

Abstract: In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function $f$ and an input string $x$, and Bob is given a function $g$ and an input string $y$. The pair $(x,y)$ comes from a known distribution $mu$ and $f$ and $g$ are guaranteed to be close under this distribution. Alice and Bob wish to compute $g(x,y)$ with high probability. The previous work showed that any problem with one-way communication complexity $k$ in the standard model has public-coin communication $O(k(1+I))$ bits in the uncertain case, where $I$ is the mutual information between $x$ and $y$. A lower bound of $Omega(sqrtI)$ bits on the public-coin uncertain communication was also shown. An important question that was left open is the power that public randomness brings to uncertain communication. Can Alice and Bob achieve efficient communication amid uncertainty without using public randomness? How powerful are public-coin protocols in overcoming uncertainty? Motivated by these two questions: - We prove the first separation between private-coin uncertain communication and public-coin uncertain communication. We exhibit a function class for which the communication in the standard model and the public-coin uncertain communication are $O(1)$ while the private-coin uncertain communication is a growing function of the length $n$ of the inputs. - We improve the lower-bound of the previous work on public-coin uncertain communication. We exhibit a function class and a distribution (with $Iapproxn$) for which the one-way certain communication is $k$ bits but the one-way public-coin uncertain communication is at least $Omega(sqrtkcdotsqrtI)$ bits.

Full work available at URL: https://arxiv.org/abs/1705.01082

zbMATH Keywords

uncertaintylower boundscommunication complexityrandomnessimperfectly shared randomness

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11)

Cited In (3)

• Communication with contextual uncertainty
• Title not available (Why is that?)
• Naor-Yung Paradigm with Shared Randomness and Applications

   Recommendations

• On the Role of Shared Randomness in Simultaneous Communication 👍 👎
• Communication With Imperfectly Shared Randomness 👍 👎
• Communication with Imperfectly Shared Randomness 👍 👎
• LATIN 2004: Theoretical Informatics 👍 👎
• Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation 👍 👎
• Common randomness in information theory and cryptography. I. Secret sharing 👍 👎
• Title not available (Why is that?) 👍 👎
• A communication-randomness tradeoff for two-processor systems 👍 👎
• Title not available (Why is that?) 👍 👎
• The Optimal Use of Rate-Limited Randomness in Broadcast Channels With Confidential Messages 👍 👎

This page was built for publication: The Power of Shared Randomness in Uncertain Communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111380)