Communication with contextual uncertainty

DOI10.1007/S00037-017-0161-3zbMATH Open1403.68061arXiv1504.04813OpenAlexW3015210772MaRDI QIDQ1616619FDOQ1616619

Authors: Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan 

Publication date: 7 November 2018

Published in: Computational Complexity, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob wishes to compute some function $g(x,y)$ (with high probability over $(x,y)$). In our variant, Alice does not know $g$, but only knows some function $f$ which is an approximation of $g$. Thus, the function being computed forms the context for the communication, and knowing it imperfectly models (mild) uncertainty in this context. A naive solution would be for Alice and Bob to first agree on some common function $h$ that is close to both $f$ and $g$ and then use a protocol for $h$ to compute $h(x,y)$. We show that any such agreement leads to a large overhead in communication ruling out such a universal solution. In contrast, we show that if $g$ has a one-way communication protocol with complexity $k$ in the standard setting, then it has a communication protocol with complexity $O(kcdot(1+I))$ in the uncertain setting, where $I$ denotes the mutual information between $x$ and $y$. In the particular case where the input distribution is a product distribution, the protocol in the uncertain setting only incurs a constant factor blow-up in communication and error. Furthermore, we show that the dependence on the mutual information $I$ is required. Namely, we construct a class of functions along with a non-product distribution over $(x,y)$ for which the communication complexity is a single bit in the standard setting but at least $Omega(sqrtn)$ bits in the uncertain setting.

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

Recommendations

• Communication with contextual uncertainty
• The Power of Shared Randomness in Uncertain Communication
• Individual communication complexity
• Deterministic compression with uncertain priors
• Deterministic compression with uncertain priors

zbMATH Keywords

uncertaintycontextcommunication complexityreliable communication

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Communication Complexity
• Probability and Computing
• An information statistics approach to data stream and communication complexity
• Title not available (Why is that?)
• On randomized one-round communication complexity
• The Communication Complexity of Correlation
• The communication complexity of the Hamming distance problem
• Deterministic compression with uncertain priors
• Communication complexity of permutation-invariant functions
• The information complexity of Hamming distance
• Massive online teaching to bounded learners
• Communication with imperfectly shared randomness
• Title not available (Why is that?)
• The Power of Shared Randomness in Uncertain Communication
• On the role of shared randomness in simultaneous communication
• On Extracting Common Random Bits From Correlated Sources
• A theory of goal-oriented communication

Cited In (9)

• Pragmatics of uncertainty
• Ambiguity and communication
• Title not available (Why is that?)
• Communication with contextual uncertainty
• Topical communication uncertainties
• Universal semantic communication
• A theory of goal-oriented communication
• Deterministic compression with uncertain priors
• Semantic communication for simple goals is equivalent to on-line learning

This page was built for publication: Communication with contextual uncertainty

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