TY - GEN

T1 - Communication with contextual uncertainty

AU - Ghazi, Badih

AU - Komargodski, Han

AU - Kothari, Pravesh

AU - Sudan, Madhu

N1 - Publisher Copyright:
© Copyright (2016) by SIAM: Society for Industrial and Applied Mathematics.

PY - 2016

Y1 - 2016

N2 - 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/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/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 0(k (1 +/)) in the uncertain setting, where/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/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 Q, (<Jn) bits in the uncertain setting.

AB - 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/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/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 0(k (1 +/)) in the uncertain setting, where/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/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 Q, (<Jn) bits in the uncertain setting.

UR - http://www.scopus.com/inward/record.url?scp=84963616087&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963616087&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974331.ch144

DO - 10.1137/1.9781611974331.ch144

M3 - Conference contribution

AN - SCOPUS:84963616087

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2072

EP - 2085

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -