Our proofs introduce new problems in the standard communication complexity model and prove lower bounds for these problems. Both the problems and the lower bound techniques may be of general interest.

In many forms of communication (e.g., human, computer-to-computer), the communicating parties share some context (e.g, knowledge of a language, operating system, communication protocol, encoding/decoding mechanisms.). This context is usually a) huge and b) imperfectly shared among the parties. Nevertheless, in human communication, very efficient communication is usually possible. Can we come up with a mathematical analogue of this phenomenon of efficient communication based on a huge but imperfectly shared context? Motivated by this general question, the study of "communication amid uncertainty" has been the subject of a series of recent work starting with Goldreich, Juba and Sudan [13,8] followed by [12,14,15,11,4]. While early works were very abstract and general, later works (starting with Juba, Kalai, Khanna and Sudan [12]) tried to explore the ramifications of uncertainty in Yao's standard communication complexity model [26]. In particular, the more recent works relax the different pieces of context that were assumed to be perfectly shared in Yao's model, such as shared randomness [4], and in a recent work of the authors with Komargodski and Kothari the function being computed [6].

Specifically, [6] study the following functional notion of uncertainty in communication. Their setup builds on -and generalizes -Yao's classical model of (distributional) communication complexity, where Alice has an input x and Bob has an input y, with (x, y) being sampled from a distribution µ. Their goal is to communicate minimally so as to compute some function g(x, y) (with high probability over the choice of (x, y)). The understated emphasis of the model is that for many functions g, the communication required is much less than the lengths of x or y, the entropy of x or y or even the conditional entropy of x given y.

The question studied by [6] is: How much of this gain in communication is preserved when the communicating parties do not exactly agree on the function being computed? (We further discuss the importance of this question in Section 1.2.) This variation of the problem is modelled as follows: Alice is given a Boolean function f and an input string x, and Bob is given a Boolean function g and an input string y where (x, y) is sampled from a known distribution µ as before, and (f, g) is chosen (adversarially) from a known class F of pairs of functions that are close in terms of the Hamming distance ∆ µ (weighted according to µ). Alice and Bob wish to compute g(x, y). Alice's knowledge of the function f (which is close but not necessarily equal to g) captures the uncertainty in the knowledge of the context.

We define the public-coin uncertain communication complexity PubCCU µ (F ) as the minimum length of a two-way public-coin protocol whose output is correct with probability at least 1 -over its internal randomness and that of (x, y). We similarly define the private-coin uncertain communication complexity PrivCCU µ (F ) by restricting to private-coin protocols. Clearly, PubCCU µ (F ) ≤ PrivCCU µ (F ). The quantities owPubCCU µ (F ) and owPrivCCU µ (F ) are similarly defined by restricting to one-way protocols. 2The previous work ( [6]) gave an upper bound on owPubCCU µ (F ) whenever F consists of functions g whose one-way distributional complexity is small. More precisely, denote by owCC µ (g) the one-way communication complexity of g in the standard distributional model. 3 Namely, owCC µ (g) is the minimum length of a one-way deterministic protocol computing g with probability at least 1 -over the randomness of (x, y). Then, [6] showed that if F consists of pairs (f, g) of functions that are at distance δ, and if owCC µ (f ), owCC µ (g) ≤ k, then for every positive θ, owPubCCU µ +2δ+θ (F) ≤ O θ (k • (1 + I(x; y))), where I(x; y) denotes the mutual information between x and y. 4 Note that if µ is a product distribution and if we let the parameter θ be a small constant, then the blow-up in communication is only a constant factor. However, the protocol of [6] crucially uses public randomness, and one of the main motivations behind this work is to understand how large the blow-up would be in the case where Alice and Bob have access to weaker types of randomness (or no randomness at all).

We point out that understanding the type of randomness that is needed in order to cope with uncertainty is a core question in the setup of communication with contextual uncertainty: If Alice and Bob do not (perfectly) agree on the function being computed, why can we assume that they (perfectly) agree on the shared randomness?

We prove several results about the power of shared randomness in uncertain communication.

Our first result (Theorem 1) shows that private-coin protocols are much weaker than publiccoin protocols in the setup of communication with contextual uncertainty. Far from obtaining a constant factor blow-up in communication, private-coin protocols incur an increase that is a growing function of n when dealing with uncertainty.

Let U U 2n be the uniform distribution on {0, 1} 2•n . For positive integers t and n, we define log (t) (n) by setting log (1) (n) = log n, and log (i) (n) = max(log log (i-1) (n), 1) for all i ∈ {2, . . . , t}.

Theorem 1 (Lower-bound on private-coin uncertain protocols). For every sufficiently small δ > 0, there exist a positive integer (δ) and a function class F F δ such that (i) For each (f, g) ∈ F , we have that ∆ U (f, g) ≤ δ. (ii) For each (f, g) ∈ F , we have that owCC U 0 (f ), owCC U 0 (g) ≤ . (iii) For every η > 0 and ∈ (4δ, 0.5], we have that

In Theorem 1, the inputs x and y are binary strings of length n and F is a family of pairs of functions, which each function mapping {0, 1} n × {0, 1} n to {0, 1}. Also, the parameter η can also be viewed as a particular case of Yao's model via an exponential blow-up in the input size. For more on this view (which turns out to be ineffective in our setup), we refer the reader to Note 9 at the end of this section. 3 By the "easy direction" of Yao's min-max principle, we can without loss of generality consider deterministic (instead of public-coin) protocols when defining owCC µ (g). We point out that this is not true in the uncertain case. 4 One interpretation of the dependence of the communication in the uncertain setup on the mutual information I(x; y) is that the players are better able to use the correlation of their inputs in the standard case than in the uncertain case.

I C A L P 2 0 1 7

The Power of Shared Randomness in Uncertain Communication can possibly depend on n. We point out that Theorem 1 also implies the first separation between deterministic uncertain protocols and public-coin uncertain protocolsfoot_1 .

Note 2. We point out that the relative power of private-coin and public-coin protocols in the uncertain model is both conceptually and technically different from the standard model. Specifically, the randomness is potentially used in the standard model in order to fool an adversary selecting the input pair (x, y), whereas in the uncertain model, it is used to fool an adversary selecting the pair (f, g) of functions that are promised to be close. This promise makes the task of proving lower bounds against private-coin protocols in the uncertain model (e.g., Theorem 1) significantly more challenging than in the standard model. 6 Moreover, a well-known theorem due to Newman [21] shows that in the standard model, any public-coin protocol can be simulated by a private-coin protocol while increasing the communication by an additive O(log n) bits. By contrast, there is no known analogue of Newman's theorem in the uncertain case! Note 3. The construction that we use to prove Theorem 1 cannot give a separation larger than Θ(log log n). Thus, showing a separation of ω(log log n) between private-coin and public-coin protocols in the uncertain case would require a new construction. For more details, see Note 13.

In light of Theorem 1, it is necessary for Alice and Bob to share some form of randomness in order to only incur a constant blow-up in communication for product distributions. Fortunately, it turns out that it is not necessary for Alice and Bob to perfectly share a sequence of random coins. If Alice is given a uniform-random string r of bits and Bob is given a string r obtained by independently flipping each coordinate of r with probability 0.49, then efficient communication is still possible! More formally, for ρ ∈ [0, 1], define owIsrCCU µ ,ρ (F ) in the same way that we defined owPubCCU µ (F ) except that instead of Alice and Bob having access to public randomness, Alice will have access to a sequence r of independent uniformly-random bits, and Bob will have access to a sequence r of bits obtained by independently flipping each coordinate of r with probability (1 -ρ)/2. Note that this setup of imperfectly shared randomness interpolates between the public randomness and private randomness setups, i.e., owIsrCCU µ ,1 (F ) = owPubCCU µ (F ) and owIsrCCU µ ,0 (F ) = owPrivCCU µ (F ).

Theorem 4 (Uncertain protocol using imperfectly shared randomness). Let ρ ∈ (0, 1] and µ be a product distribution. Let F consist of pairs (f, g) of functions with ∆ µ (f, g) ≤ δ, and owCC µ (f ), owCC µ (g) ≤ k. Then, for every positive θ,

The imperfectly shared randomness model in Theorem 4 was recently independently introduced (in the setup of communication complexity) by Bavarian, Gavinsky and Ito [2] and by Canonne, Guruswami, Meka and Sudan [4] (and it was further studied in [5]). Moreover, our proof of Theorem 4 is based on combining the uncertain protocol of [6] and the locality-sensitive-hashing based protocol of [4].

We point out that Theorem 4 also holds for more general i.i.d. sources of correlated randomness than the one described above. More precisely, for i.i.d. (not necessarily binary) sources of (imperfectly) shared randomness with maximal correlation 7 ρ, the work of Witsenhausen [24] along with the protocols of [4] and [6] imply an uncertain protocol with O θ (k/ρ 2 ) bits of communication.

We now turn to our next result where we consider the dependence of the upper bound of [6] on the mutual information I I(X; Y ) in the case of public-coin protocols. The previous work [6] proved a lower bound of Ω( √ I) on this dependence, but their lower-bound does not grow with k. We improve this lower bound to Ω(

Theorem 5 (Improved lower-bound on public-coin uncertain protocols). For every sufficiently small δ > 0 and every positive integers k, n

for some absolute constant > 0 independent of δ.

As will be explained in detail in Section 2.2, the proof of Theorem 5 is based on an extension of the lower bound construction of [6], which is then analyzed using different techniques.

Our lower bounds in Theorems 1 and 5 are derived by defining new problems in standard communication complexity (i.e., without uncertainty) and proving lower bounds for these problems. We describe these problems and our results on these next.

The construction that we use to prove Theorem 1 requires us to understand the following "subset-majority with side information" setup. Alice is given a subset S ⊆ [n] and a string x ∈ {±1} n , and Bob is given a subset T ⊆ [n] and a string y ∈ {±1} n . The subsets S and T are adversarially chosen but are promised to satisfy S ⊆ T , |T | = and |T \S| ≤ δ• for some fixed parameters and δ. The strings x and y are chosen independently and uniformly at random. Alice and Bob wish to compute the function SubsetMaj((S, x), (T, y)) Sign( i∈T x i y i ). In words, SubsetMaj((S, x), (T, y)) is equal to 0 if x and y differ on a majority of the coordinates in subset T , and 1 otherwise. Note that S does not directly appear in the definition of the function SubsetMaj but it can serve as useful side-information for Alice. 9 What is the private-coin communication complexity of computing SubsetMaj on every (S, T )-pair satisfying the above promise and with high probability over the random choice of (x, y) and over the private randomness? We prove the following (informally stated) lower bound. 7 The maximal correlation of a pair (X, Y ) of random variables (with support X × Y) is defined as

where the supremum is over all functions F :

It is not hard to show that the binary source of imperfectly shared randomness defined in the paragraph preceding Theorem 4 has maximal correlation ρ. 8 We note that I ≈ k • n means that I/(k • n) → 0 as n → ∞. 9 Note that we could have alternatively defined SubsetMaj in terms of S, and let T serve as the potentially useful side-information. Our lower bound would also apply to this setup.

I C A L P 2 0 1 7

The Power of Shared Randomness in Uncertain Communication Lemma 7. Any private-coin protocol computing SubsetMaj on every (S, T )-pair satisfying the promise and with high probability over the random choice of (x, y) and over the private randomness should communicate at least log (t) (n) bits for some positive integer t that depends on δ and the error probability.

The proof of Theorem 5 is based on a construction that leads to the question described next regarding the communication complexity of a particular block-composed function. Namely, consider the following "majority composed with subset-parity with side information" setup. Alice is given a sequence of subsets S (S (i) ⊆ [n]) i∈ [k] and a sequence of strings

and Bob is given a sequence of subsets T (T (i) ⊆ [n]) i∈[k] and a sequence of strings y (y (i) ∈ {0, 1} n ) i∈ [k] . We consider the following distribution µ on ((S, x), (T, y)). Independently for each i ∈ [k], we sample ((S (i) , x (i) ), (T (i) , y (i) )) as follows: S (i) is a uniform-random subset and T (i) is an -noisyfoot_3 copy of S (i) , and independently x (i) is a uniform-random string and y (i) is an -noisy copy of x. Here, is a positive parameter that can depend on n and k. Alice and Bob wish to compute the function Maj • SubsetParity((S, x), (T, y)) Sign k i=1 (-1) T (i) ,x (i) ⊕y (i) where T (i) denotes both the subset and its 0/1 indicator vector, the inner product is over F 2 , and x (i) ⊕ y (i) is the coordinate-wise XOR of x (i) and y (i) . What is the communication complexity of computing Maj • SubsetParity with high probability over the distribution µ? We prove the following lower bound.

In Section 2.1, we outline the proof of Theorem 1 and explain how it leads to the setup of Lemma 7 and how we prove Lemma 7. In Section 2.2, we outline the proof of Theorem 5 and explain how it leads to the setup of Lemma 8 and how we prove Lemma 8.

Before doing so, we discuss some conceptual implications of our results.

Functional uncertainty models much of the day-to-day interactions among humans, where a person is somewhat aware of the objectives of the other person she is interacting with, but do not know them precisely. Neither person typically knows exactly what aspects of their own knowledge may be relevant to the interaction, yet they do manage to have a short conversation. This is certainly a striking phenomenon, mostly unexplained in mathematical terms. This line of works aims to explore such phenomena. It is important to understand what mechanisms may come into play here, and what features play a role. Is the ability to make random choices important? Is shared information crucial? Is there a particular measure of distance between functions that makes efficient communication feasible? In order to understand such questions, one first needs to have a ground-level understanding of communication with functional uncertainty. This work tackles several basic questions that remain unexplored. An ideal model for communication would only assume a constant amount of perfectly shared context between the sender and receiver, such as the knowledge of an encoding/decoding algorithm, one universal Turing machine, etc. Solutions to most interesting communication problems seem to assume a shared information which grows with the length of the inputs.

Recent work showed that in many of these scenarios some assumptions about the shared context can be relaxed to an imperfect sharing, but these results are often brittle and break when two or more contextual elements are simultaneously assumed to be imperfectly shared. Our work raises the question of whether imperfectly shared randomness would be sufficient to overcome functional uncertainty. We show that this is indeed the case for product distributions, but the loss for non-product distributions might be much larger (for this and other open questions, we refer the reader to our conclusion Section 6). Such results highlight the delicate nature of the role of shared context in communication. They beg for a more systematic study of communication which at the very least should be able to mimic the aims, objectives and phenomena encountered in human communication.

Note 9. As mentioned in Footnote 2, the uncertain model is clearly a generalization of Yao's model. Strictly speaking, the uncertain model can also be viewed as a particular case of Yao's model by regarding the function(s) that is being computed as part of the inputs of Alice and Bob, which results in an exponential blow-up in the input-size. This latter view turns out to be fruitless for our purposes. Indeed, from this perspective, all the different well-studied communication functions (such as Equality, Set Disjointness, Pointer Jumping, etc.) are regarded as special cases of one "universal function"! More importantly, this view completely blurs the distinction between the goal of the communication (i.e., the function to compute) and the inputs of the parties. On a technical level, it does not simplify the task of proving the lower bounds in Theorems 1 and 5 in any way since it does not capture the promise that the two functions (given to Alice and Bob) are close in Hamming distance. Thus, in the rest of this paper, we stick to the former view and use the expressions "uncertain model" and "standard model" to refer to the setups with and without uncertainty, respectively.

Overview of Proofs

Reduction to Lemma 7

In order to prove Theorem 1, we need to devise a function class for which circumventing the uncertainty is much easier using public randomness than using private randomness. One general setup in which Bob can leverage public randomness to resolve some uncertainty regarding Alice's knowledge is the following "small-set intersection" problem. Assume that Alice is given a subset S ⊆ [n], and Bob is given a subset T ⊆ [n] such that T contains S and |T | = , where we think of as being a large constant. Here, Bob knows that Alice has a subset of his own T but he is uncertain which subset Alice has. Using public randomness, a standard 1-way hashing protocol communicating Õ( ) bits allows Bob to determine S with high probability. On the other hand, using only private randomness, the communication complexity of this task is Θ(log log n) bits.

With the above general setup in mind, we consider functions f S indexed by small subsets S of coordinates on which they depend. Since we want the functions f S and f T to be close in Hamming distance, we enforce |T \ S| to be small for every pair (f S , f T ) of functions in our class, and we let each function f S be "noise-stable". Since we want our function f S to genuinely depend on all coordinates in S, the majority function f S (x, y) = Sign( i∈S x i y i ) for x, y ∈ {±1} n arises as a natural choice. We also let x and y be independent uniformrandom strings. In this case, it can be seen that if |T \ S| is a small constant fraction of |T |, then the quadratic polynomials i∈S x i y i and i∈T x i y i behave like standard Gaussians with correlation close to 1, and the quadratic threshold functions f S (x, y) and f T (x, y) are thus close in Hamming distance.

Note that in the certain case, i.e., when both Alice and Bob agree on S, they can easily compute f S (x, y) by having Alice send to Bob the bits (x i ) i∈S . Moreover, if Alice and Bob are given access to public randomness in the uncertain case, Bob can figure out S via the hashing protocol mentioned above using Õ( ) bits of communication, which would reduce the problem to the certain case 11 . The bulk of the proof will be to lower-bound the private-coin uncertain communication. Note that by the choice of our function class and distribution, this is equivalent to proving Lemma 7.

To prove Lemma 7, the high-level intuition is that a protocol solving the uncertain problem should be essentially revealing to Bob the subset S that Alice holds. Formalizing this intuition turns out to be challenging, especially that a private-coin protocol solving the uncertain problem is only required to output a single bit which is supposed to equal the Boolean function f T (x, y) with high probability over (x, y) and over the private randomness. In fact, this high-level intuition can be shown not to hold in certain regimes 12 . Moreover, the standard proofs that lower bound the communication of small-set intersection do not extend to lower-bound the communication complexity of f T .

To lower-bound the private-coin communication of solving the uncertain task by a growing function of n, we consider the following shift communication game. Bob is given a sorted tuple σ = (σ 1 , . . . , σ t ) of integers with 1 ≤ σ 1 < • • • < σ t ≤ n, and Alice is either given the prefix (σ 1 , . . . , σ t-1 ) of length t -1 of σ or the suffix (σ 2 , . . . , σ t ) of length t -1 of σ. Bob needs to determine the input of Alice. We show that a celebrated lower bound of Linial [19] on the chromatic number of certain related graphs implies a lower bound of log (t+1) (n) on the private-coin communication of the shift communication game. We then show that any private-coin protocol solving the uncertain task can be turned into a private-coin protocol solving the shift-communication game with a constant (i.e., independent of n) blow-up in the communication.

The proof of Theorem 5 builds on the lower-bound construction of [6] which we recall next. Let µ be the distribution over pairs (x, y) ∈ {0, 1} 2n where x is uniform-random and y is an -noisy copy of x with = δ/n. Then, the mutual information between x and y satisfies I ≈ n. For each S ⊆ [n], consider the function f S (x, y) S, x ⊕ y where the inner product is over F 2 , x ⊕ y denotes the coordinate-wise XOR of x and y, and S is used to denote both the subset and its 0/1 indicator vector. Moreover, consider the class F of all pairs of functions (f S , f T ) where |S T | ≤ √ δn. It can be seen that for such S and T , the distance between f S and f T under µ is at most δ. If Alice and Bob both know S, then Alice can send the single bit S, x to Bob who can then output the correct answer S, x ⊕ y = S, x ⊕ S, y . This means that the certain communication is 1 bit. Using the well-known discrepancy method, [6] showed a lower bound of Ω( √ n) bits on the communication of the associated uncertain problem. Since in this case I ≈ n, this in fact lower-bounds the uncertain communication by Ω( √ I) bits. For this construction, this lower bound turns out to be tight up to a logarithmic factor.

To improve the lower-bound from √ I to √ k • √ I, we consider the following "blockcomposed" framework. Let {f S (i) (x (i) , y (i) ) : i ∈ [k]} be k independent copies of the above base problem of [6] and consider computing the composed function g f S (1) (x (1) , y (1) ), . . . , f S (k) (x (k) , y (k) ) for some outer function g : {0, 1} k → {0, 1}. For any choice of g, the certain communication of the composed function would be at most k bits. When choosing the outer function g to use in our lower bound, we thus have two objectives to satisfy. First, g has to be sufficiently hard in the sense that its average-case decision tree complexity with respect to the uniform distribution on {0, 1} k should be Ω(k); otherwise, it will not be the case that the uncertain communication of computing g on k copies of the base problem is at least k times the uncertain communication of the base problem. Second, g has to be noise stable in order to be able to upper bound the distance between g f S

Note that setting g to be a dictator function would satisfy the noise-stability property, but it clearly would not satisfy the hardness property, as the composed function would be equal to the base function and would thus have uncertain communication Õ( √ n) bits. Another potential choice of g is to set it to the parity function on k bits. This function would satisfy the hardness property, but it would strongly violate the noise stability property that is crucial to us. This leads us to setting g to the majority function on k bits, which is well-known to be noise stable, and has average-case decision-tree complexity Ω(k) with respect to the uniform distribution on {0, 1} k . In fact, the noise stability of the majority function readily implies an upper bound of O( √ δ) on the distance between any pair of composed functions that are specified by tuples of subsets (S (1) , . . . , S (k) ) and (T (1) , . . . , T (k) ) with |S

We first point out that the average-case quantum decision tree complexity of Maj k with respect to the uniform distribution is Õ( √ k) [1]. This implies that any communication complexity lower-bound method that extends to the quantum model cannot prove a lower bound larger than Õ( √ k • √ n) on our uncertain communication 13 . In particular, we cannot solely rely on the discrepancy bound (as done in [6]), since this bound is known to lower-bound quantum communication. Similarly, the techniques of [22,23,18] rely on the generalized discrepancy bound (originally due to [16]) which also lower-bounds quantum communication. Moreover, the recent results of [20] only apply to product distributions (i.e., where Alice's input is independent of Bob's input) in contrast to our case where the inputs of Alice and Bob are very highly-correlated. Finally, the recent works of [9, 10] do not imply lower bounds on the average-case complexity with respect to the distribution that arises in our setup.

To circumvent the above obstacles, we use a new approach that is tailored to our setup and that is outlined next. Let Π be a 1-way protocol solving the uncertain task with high probability. We consider the information that Π reveals about the inputs to the outer to use public randomness, no non-trivial protocols are known in this setting. On the other hand, no separations are known for this case (beyond those known for r = 1) even if the protocols are restricted to be deterministic.