# 6 Conclusion

In Theorem 2 we have proven a lower bound for communication complexity of protocols with private randomness. The argument can be extended to the setting where Alice and Bob use both private and public random bits (the private sources of randomness are available only to Alice and Bob respectively; the public source of randomness is available to both parties and to the eavesdropper). Thus, the problem of the worst case complexity is resolved for the most general natural model of communication.

For pairs of inputs $(x, y)$ from Example 1 and Example 2 (corresponding to edges of a graph with a large spectral gap) we have got a lower bound for communication complexity that matches the known upper bound. However, in the known protocols achieving this bound the communication is very non-symmetric: all (or almost all) the burden of communication falls on only one of two participants. We do not know whether there exist more balanced protocols, where the communication complexity is shared equally between Alice and Bob.

We have no characterization of the optimal communication complexity of the secret key agreement for pairs of inputs $(x, y)$ that do not enjoy the spectral property required in Corollary 1. In particular, there is a large gap between constant hidden in the $O(\delta n)$ notation in Theorem 3 and in the $\Omega(\delta n)$ notation in and Theorem 4, so the question on the optimal trade-off between the secret key size and communication complexity for $(x, y)$ from Example 3 remains open (cf. Conjecture 1 in [19] for an analogous problem in Shannon's setting).

In some applications (see, e.g., [7, 14]) it is natural to assume that the eavesdropper is given a non-negligible *a priori* information about Alice' and Bob's inputs. For this setting we do not have a characterization of the optimal size of the key and the communication complexity of the protocol.

**Acknowledgements** The authors thank the anonymous reviewers of the conference MFCS 2020 for instructive suggestions and corrections concerning this conference publication as well as the full version of the paper. The second author is grateful to the Max Planck Institute for Mathematics in the Sciences (Leipzig, Germany) for hospitality, and thanks Rostislav Matveev and Jacobus Portegies for useful discussions.

# References

[1] Rudolf Ahlswede and Imre Csiszár. Common randomness in information theory and cryptography. I. Secret sharing. *IEEE Transactions on Information Theory*, 39(4):1121–1132, 1993.

[2] Noga Alon and Joel H. Spencer. *The probabilistic method*. John Wiley & Sons, 2004.

[3] Luis Antunes, Sophie Laplante, Alexandre Pinto, and Liliana Salvador. Cryptographic security of individual instances. In *International Conference on Information Theoretic Security*, pages 195–210. Springer, 2007.

[4] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer, and Matt McGinnis. The smallest eigenvalues of hamming graphs, johnson graphs and other distance-regular graphs with classical parameters. *Journal of Combinatorial Theory, Series B*, 133:88–121, 2018.

[5] Harry Buhrman, Lance Fortnow, and Sophie Laplante. Resource-bounded kolmogorov complexity revisited. *SIAM Journal on Computing*, 31(3):887–905, 2001.

[6] Alexei Chernov, Andrej Muchnik, Andrei Romashchenko, Alexander Shen, and Nikolai Vereshchagin. Upper semi-lattice of binary strings with the relation “x is simple conditional to y”. *Theoretical Computer Science*, 271(1-2):69–95, 2002.

[7] Igor Devetak and Andreas Winter. Distillation of secret key and entanglement from quantum states. *Proceedings of the Royal Society A: Mathematical, Physical and engineering sciences*, 461(2053):207–235, 2005.

[8] Whitfield Diffie and Martin Hellman. New directions in cryptography. *IEEE Transactions on Information Theory*, 22(6):644–654, 1976.
[9] Shai Evra, Konstantin Golubev, and Alexander Lubotzky. Mixing properties and the chromatic number of ramanujan complexes. *International Mathematics Research Notices*, 2015(22):11520–11548, 2015.

[10] Peter Grünwald and Paul Vitányi. Shannon information and kolmogorov complexity. *arXiv preprint arXiv:0410002*, 2004.

[11] Daniel Hammer, Andrei Romashchenko, Alexander Shen, and Nikolai Vereshchagin. Inequalities for shannon entropy and kolmogorov complexity. *Journal of Computer and System Sciences*, 60(2):442–464, 2000.

[12] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. *Journal of the American Statistical Association*, 58(301):13–30, 1963.

[13] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. *Bulletin of the American Mathematical Society*, 43(4):439–561, 2006.

[14] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. *Reviews of modern physics*, 81(2):865, 2009.

[15] Tanya Ignatenko and Frans MJ Willems. Biometric security from an information-theoretical perspective. *Foundations and Trends® in Communications and Information Theory*, 7(2–3):135–316, 2012.

[16] Tarik Kaced, Andrei Romashchenko, and Nikolai Vereshchagin. A conditional information inequality and its combinatorial applications. *IEEE Transactions on Information Theory*, 64(5):3610–3615, 2018.

[17] Eyal Kushilevitz and Noam Nisan. *Communication Complexity*. Cambridge University Press, 2006.

[18] Ming Li and Paul Vitányi. *An introduction to Kolmogorov complexity and its applications*. Springer, 4 edition, 2019.

[19] Jingbo Liu, Paul Cuff, and Sergio Verdú. Secret key generation with limited interaction. *IEEE Transactions on Information Theory*, 63(11):7358–7381, 2017.

[20] Xiaogang Liu and Sanming Zhou. Eigenvalues of cayley graphs. *arXiv preprint arXiv:1809.09829*, 2018.

[21] Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, and Nikolai Vereshchagin. A new class of non-shannon-type inequalities for entropies. *Communications in Information and Systems*, 2(2):147–166, 2002.

[22] Ueli M. Maurer. Secret key agreement by public discussion from common information. *IEEE transactions on information theory*, 39(3):733–742, 1993.

[23] Archie Medrano, Perla Myers, Harold M. Stark, and Audrey Terras. Finite analogues of euclidean space. *Journal of Computational and Applied Mathematics*, 68(1-2):221–238, 1996.

[24] An A Muchnik. On common information. *Theoretical Computer Science*, 207(2):319–328, 1998.

[25] Andrej A. Muchnik. Conditional complexity and codes. *Theoretical Computer Science*, 271(1-2):97–109, 2002.

[26] Daniil Musatov, Andrei Romashchenko, and Alexander Shen. Variations on muchnik's conditional complexity theorem. *Theory of Computing Systems*, 49(2):227–245, 2011.

[27] Jitsuro Nagura. On the interval containing at least one prime number. *Proceedings of the Japan Academy*, 28(4):177–181, 1952.

[28] Ilan Newman. Private vs. common random bits in communication complexity. *Information processing letters*, 39(2):67–71, 1991.

[29] Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In *Proceedings 41st Annual Symposium on Foundations of Computer Science*, pages 3–13. IEEE, 2000.
[9] Shai Evra, Konstantin Golubev, and Alexander Lubotzky. Mixing properties and the chromatic number of ramanujan complexes. *International Mathematics Research Notices*, 2015(22):11520–11548, 2015.

[10] Peter Grünwald and Paul Vitányi. Shannon information and kolmogorov complexity. *arXiv preprint arXiv:0410002*, 2004.

[11] Daniel Hammer, Andrei Romashchenko, Alexander Shen, and Nikolai Vereshchagin. Inequalities for shannon entropy and kolmogorov complexity. *Journal of Computer and System Sciences*, 60(2):442–464, 2000.

[12] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. *Journal of the American Statistical Association*, 58(301):13–30, 1963.

[13] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. *Bulletin of the American Mathematical Society*, 43(4):439–561, 2006.

[14] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. *Reviews of modern physics*, 81(2):865, 2009.

[15] Tanya Ignatenko and Frans MJ Willems. Biometric security from an information-theoretical perspective. *Foundations and Trends® in Communications and Information Theory*, 7(2–3):135–316, 2012.

[16] Tarik Kaced, Andrei Romashchenko, and Nikolai Vereshchagin. A conditional information inequality and its combinatorial applications. *IEEE Transactions on Information Theory*, 64(5):3610–3615, 2018.

[17] Eyal Kushilevitz and Noam Nisan. *Communication Complexity*. Cambridge University Press, 2006.

[18] Ming Li and Paul Vitányi. *An introduction to Kolmogorov complexity and its applications*. Springer, 4 edition, 2019.

[19] Jingbo Liu, Paul Cuff, and Sergio Verdú. Secret key generation with limited interaction. *IEEE Transactions on Information Theory*, 63(11):7358–7381, 2017.

[20] Xiaogang Liu and Sanming Zhou. Eigenvalues of cayley graphs. *arXiv preprint arXiv:1809.09829*, 2018.

[21] Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, and Nikolai Vereshchagin. A new class of non-shannon-type inequalities for entropies. *Communications in Information and Systems*, 2(2):147–166, 2002.

[22] Ueli M. Maurer. Secret key agreement by public discussion from common information. *IEEE transactions on information theory*, 39(3):733–742, 1993.

[23] Archie Medrano, Perla Myers, Harold M. Stark, and Audrey Terras. Finite analogues of euclidean space. *Journal of Computational and Applied Mathematics*, 68(1-2):221–238, 1996.

[24] An A Muchnik. On common information. *Theoretical Computer Science*, 207(2):319–328, 1998.

[25] Andrej A. Muchnik. Conditional complexity and codes. *Theoretical Computer Science*, 271(1-2):97–109, 2002.

[26] Daniil Musatov, Andrei Romashchenko, and Alexander Shen. Variations on muchnik's conditional complexity theorem. *Theory of Computing Systems*, 49(2):227–245, 2011.

[27] Jitsuro Nagura. On the interval containing at least one prime number. *Proceedings of the Japan Academy*, 28(4):177–181, 1952.

[28] Ilan Newman. Private vs. common random bits in communication complexity. *Information processing letters*, 39(2):67–71, 1991.

[29] Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In *Proceedings 41st Annual Symposium on Foundations of Computer Science*, pages 3–13. IEEE, 2000.
[30] Andrei Romashchenko and Marius Zimand. An operational characterization of mutual information in algorithmic information theory. *Journal of the ACM (JACM)*, 66(5):1–42, 2019.

[31] Andrei E. Romashchenko. Pairs of words with nonmaterializable mutual information. *Problems of Information Transmission*, 36(1), 2000.

[32] Alexander Shen, Vladimir Uspensky, and Nikolay Vereshchagin. *Kolmogorov complexity and algorithmic randomness*, volume 220. American Mathematical Soc., 2017.

[33] Madhu Sudan, Himanshu Tyagi, and Shun Watanabe. Communication for generating correlation: A unifying survey. *IEEE Transactions on Information Theory*, 66(1):5–37, 2019.

[34] Himanshu Tyagi. Common information and secret key capacity. *IEEE Transactions on Information Theory*, 59(9):5627–5640, 2013.

[35] Le Anh Vinh. The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields. *European Journal of Combinatorics*, 32(8):1177–1181, 2011.

[36] Alexander K. Zvonkin and Leonid A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. *Russian Mathematical Surveys*, 25(6):83, 1970.

[37] Rustam Zyavgarov. Private communication, May 2022.

## A Technical Lemmas and a Proof of Proposition 1

In this section we prove a version of Newman’s theorem (on sampling random bits) for communication protocols with private randomness. We start with two technical lemmas and then proceed with a proof of Proposition 1.

**Definition 1.** Let $R_A$ and $R_B$ be finite sets and let $S \subset A \times B$. We say that a sequence (or a multiset) of elements $a_1, \dots, a_k$ in $A$ and a sequence (multiset) of elements $b_1, \dots, b_k$ in $B$ provide a $\delta$-precise sampling of $S$ in $A \times B$ if

$$ \left| \mathrm{Prob}_{i,j}[(a_i, b_j) \in S] - \frac{|S|}{|A \times B|} \right| < \delta, $$

see Fig. 7.

**Lemma 13.** Let $A$ and $B$ be finite sets and let $S \subset A \times B$. We choose at random sequences of elements $a_1, \dots, a_k$ in $A$ and $b_1, \dots, b_k$ in $B$ (all $a_i$ and $b_j$ are independent and uniformly distributed on $A$ and $B$ respectively). Then with probability at least $1 - 4e^{-\delta^2 k/2}$ the chosen pair of sequences provides a $\delta$-precise sampling of $S$.

*Proof.* To prove the lemma, we split the process of sampling in two steps. At first, we substitute $A$ by a sequence $a_1, \dots, a_k$ and estimate the difference

$$ \left| \mathrm{Prob}_{i \in \{1, \dots, k\}, b \in B}[(a_i, b) \in S] - \mathrm{Prob}_{a \in A, b \in B}[(a, b) \in S] \right|, \qquad (19) $$

see Fig. 8. Then, we fix a sequence $a_1, \dots, a_k$, choose at random a sequence $b_1, \dots, b_k \in B$ and estimate the difference

$$ \left| \mathrm{Prob}_{i \in \{1, \dots, k\}, j \in \{1, \dots, k\}}[(a_i, b_j) \in S] - \mathrm{Prob}_{i \in \{1, \dots, k\}, b \in B}[(a_i, b) \in S] \right|. \qquad (20) $$

We show that both of these differences are typically small and, therefore, the difference

$$ \left| \mathrm{Prob}_{i \in \{1, \dots, k\}, j \in \{1, \dots, k\}}[(a_i, b_j)] - \mathrm{Prob}_{a \in A, b \in B}[(a, b) \in S] \right| $$

is typically small as well.

*Claim:* For a randomly chosen sequence $a_1, \dots, a_k \in A$, the probability that the difference in (19) is larger than $\delta/2$ is less than $2e^{-\delta^2 k/2}$.
[30] Andrei Romashchenko and Marius Zimand. An operational characterization of mutual information in algorithmic information theory. *Journal of the ACM (JACM)*, 66(5):1–42, 2019.

[31] Andrei E. Romashchenko. Pairs of words with nonmaterializable mutual information. *Problems of Information Transmission*, 36(1), 2000.

[32] Alexander Shen, Vladimir Uspensky, and Nikolay Vereshchagin. *Kolmogorov complexity and algorithmic randomness*, volume 220. American Mathematical Soc., 2017.

[33] Madhu Sudan, Himanshu Tyagi, and Shun Watanabe. Communication for generating correlation: A unifying survey. *IEEE Transactions on Information Theory*, 66(1):5–37, 2019.

[34] Himanshu Tyagi. Common information and secret key capacity. *IEEE Transactions on Information Theory*, 59(9):5627–5640, 2013.

[35] Le Anh Vinh. The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields. *European Journal of Combinatorics*, 32(8):1177–1181, 2011.

[36] Alexander K. Zvonkin and Leonid A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. *Russian Mathematical Surveys*, 25(6):83, 1970.

[37] Rustam Zyavgarov. Private communication, May 2022.

## A Technical Lemmas and a Proof of Proposition 1

In this section we prove a version of Newman’s theorem (on sampling random bits) for communication protocols with private randomness. We start with two technical lemmas and then proceed with a proof of Proposition 1.

**Definition 1.** Let $R_A$ and $R_B$ be finite sets and let $S \subset A \times B$. We say that a sequence (or a multiset) of elements $a_1, \dots, a_k$ in $A$ and a sequence (multiset) of elements $b_1, \dots, b_k$ in $B$ provide a $\delta$-precise sampling of $S$ in $A \times B$ if

$$ \left| \mathrm{Prob}_{i,j}[(a_i, b_j) \in S] - \frac{|S|}{|A \times B|} \right| < \delta, $$

see Fig. 7.

**Lemma 13.** Let $A$ and $B$ be finite sets and let $S \subset A \times B$. We choose at random sequences of elements $a_1, \dots, a_k$ in $A$ and $b_1, \dots, b_k$ in $B$ (all $a_i$ and $b_j$ are independent and uniformly distributed on $A$ and $B$ respectively). Then with probability at least $1 - 4e^{-\delta^2 k/2}$ the chosen pair of sequences provides a $\delta$-precise sampling of $S$.

*Proof.* To prove the lemma, we split the process of sampling in two steps. At first, we substitute $A$ by a sequence $a_1, \dots, a_k$ and estimate the difference

$$ \left| \mathrm{Prob}_{i \in \{1, \dots, k\}, b \in B}[(a_i, b) \in S] - \mathrm{Prob}_{a \in A, b \in B}[(a, b) \in S] \right|, \qquad (19) $$

see Fig. 8. Then, we fix a sequence $a_1, \dots, a_k$, choose at random a sequence $b_1, \dots, b_k \in B$ and estimate the difference

$$ \left| \mathrm{Prob}_{i \in \{1, \dots, k\}, j \in \{1, \dots, k\}}[(a_i, b_j) \in S] - \mathrm{Prob}_{i \in \{1, \dots, k\}, b \in B}[(a_i, b) \in S] \right|. \qquad (20) $$

We show that both of these differences are typically small and, therefore, the difference

$$ \left| \mathrm{Prob}_{i \in \{1, \dots, k\}, j \in \{1, \dots, k\}}[(a_i, b_j)] - \mathrm{Prob}_{a \in A, b \in B}[(a, b) \in S] \right| $$

is typically small as well.

*Claim:* For a randomly chosen sequence $a_1, \dots, a_k \in A$, the probability that the difference in (19) is larger than $\delta/2$ is less than $2e^{-\delta^2 k/2}$.
<figure><img src="image_8.png" /><figcaption>Figure 7: Sampling random points in $S \subset A \times B$ by choosing independently random columns $a_i \in A$ and random rows $b_j \in B$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 8: Restriction of a set $S \subset A \times B$ onto the product $\{a_1, \dots, a_k\} \times B$ with randomly chosen columns $a_i \in A$.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 7: Sampling random points in $S \subset A \times B$ by choosing independently random columns $a_i \in A$ and random rows $b_j \in B$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 8: Restriction of a set $S \subset A \times B$ onto the product $\{a_1, \dots, a_k\} \times B$ with randomly chosen columns $a_i \in A$.</figcaption></figure>
*Proof of the claim:* For every $a \in A$ we denote by $\varphi(a)$ the fraction of elements from $S$ in the column of the Cartesian product $A \times B$ corresponding to the value $a$, i.e.,

$$ \varphi(a) := \frac{|S \cap (\{a\} \times B)|}{|B|}. $$

From the definition it follows that $0 \le \varphi(a) \le 1$ for every $a \in A$, and the average value of $\varphi(a)$ (for a randomly chosen $a$) is equal to $\sigma := \frac{|S|}{|A \times B|}$. Since $a_1, \dots, a_k$ are chosen in $A$ independently, the values $\varphi(a_1), \dots, \varphi(a_k)$ are independent and identically distributed. Hence, we can apply Hoeffding's inequality (see [12]):

$$ \mathrm{Prob} \left[ \left| \frac{\varphi(a_1) + \dots + \varphi(a_k)}{k} - \sigma \right| \ge \delta/2 \right] \le 2e^{-2(\delta/2)^2 k}. $$

This means that with a probability $\ge 1 - 2e^{-2(\delta/2)^2 k}$ the gap (19) is less than $\delta/2$. $\square$

Let us fix now a sequence $a_1, \dots, a_k \in A$, and estimate the difference in (20) as a function of random sequence $b_1, \dots, b_k \in B$. We can use once again the same argument with Hoeffding's inequality as in Claim above, now for the sampling of values of the second coordinate in $\{a_1, \dots, a_k\} \times B$. It follows that with a probability $\ge 1 - 2e^{-\delta^2 k/2}$ the gap (20) is less than $\delta/2$. Combining the bounds for (19) and (20), we obtain the lemma. $\square$

**Lemma 14.** Let $\pi$ be a two-party communication protocol where Alice and Bob access inputs $x$ and $y$ respectively, and use private random bits $r_A \in \{0, 1\}^s$ and $r_B \in \{0, 1\}^s$ respectively. For $z_1, z_2, t$ we denote by $p(x, y, z_1, z_2, t)$ the probability of the following event: given $x$ and $y$ as inputs, Alice and Bob apply the protocol $\pi$ and end up with an answer $z_1 \in \{0, 1\}^m$ for Alice, an answer $z_2 \in \{0, 1\}^m$ for Bob, and a communication transcript $t \in \{0, 1\}^l$. The probability is taken on independent and uniformly distributed $r_A, r_B$.

We apply to $\pi$ a random transformation as follows: we choose two random sequences $a_1, \dots, a_k$ and $b_1, \dots, b_k$ in $\{0, 1\}^s$. In the new communication protocol $\pi'$ Alice and Bob choose at random $i, j \in \{1, \dots, k\}$, and then apply the original communication protocol with private strings of random bits $a_i$ and $b_j$ respectively. By construction, in the protocol $\pi'$ Alice and Bob need $\log k$ private random bits each (they both need to choose a random index between 1 and $k$).

Denote by $p'(x, y, z_1, z_2, t)$ the probability analogous to $p(x, y, z_1, z_2, t)$ computed for the protocol $\pi'$. The probability is taken on the choice of independent and uniformly distributed $i, j \in \{1, \dots, k\}$. We claim that for all $x, y, z_1, z_2, t$ the probability of the event

$$ |p(x, y, z_1, z_2, t) - p'(x, y, z_1, z_2, t)| < \delta \quad (21) $$

is greater than $1 - 4e^{-\delta^2 k/2}$ (here the probability is taken over the choice of $a_1, \dots, a_k$ and $b_1, \dots, b_k$ in $\{0, 1\}^s$ in the construction of $\pi'$).

*Proof.* We apply Lemma 13 with $A = B = \{0, 1\}^s$ (the space of random bits of the original protocol), and $S = S(x, y, z_1, z_2, t)$ that consists of the pairs $(r_A, r_B) \in \{0, 1\}^s \times \{0, 1\}^s$ compatible with the given $x, y, z_1, z_2, t$. In other words, a pair $(r_A, r_B)$ belongs to $S$, if Alice and Bob given $x$ and $y$ as inputs and $r_A$ and $r_B$ as random bits, obtain with the protocol $\pi$ answers $z_1$ and $z_2$ respectively and produce a communication transcript $t$. From the lemma it follows that with the probability $1 - 4e^{-\delta^2 k/2}$, the choice of $a_1, \dots, a_k$ and $b_1, \dots, b_k$ in $\{0, 1\}^s$ in the construction of $\pi'$ provides a $\delta$-precise sampling of $S$. $\square$

Now we are ready to prove a version of Newman's theorem suitable for our setting.

*Proof of Proposition 1.* Due to Lemma 14, with randomly chosen samples $a_1, \dots, a_k$ and $b_1, \dots, b_k$ with a probability $> 1 - 4e^{-\delta^2 k/2}$ we obtain a new protocol $\pi'$ such that for each $(x, y, z_1, z_2, t)$ we have (21). We apply this construction with a $\delta$ such that

$$ \delta := \frac{\varepsilon_2}{\#\mathrm{answers}\ z_1 \cdot \#\mathrm{answers}\ z_2 \cdot \#\mathrm{transcripts}\ t} $$
Proof of the claim: For every $a \in A$ we denote by $\varphi(a)$ the fraction of elements from $S$ in the column of the Cartesian product $A \times B$ corresponding to the value $a$, i.e.,

$$ \varphi(a) := \frac{|S \cap (\{a\} \times B)|}{|B|}. $$

From the definition it follows that $0 \le \varphi(a) \le 1$ for every $a \in A$, and the average value of $\varphi(a)$ (for a randomly chosen $a$) is equal to $\sigma := \frac{|S|}{|A \times B|}$. Since $a_1, \dots, a_k$ are chosen in $A$ independently, the values $\varphi(a_1), \dots, \varphi(a_k)$ are independent and identically distributed. Hence, we can apply Hoeffding's inequality (see [12]):

$$ \mathrm{Prob} \left[ \left| \frac{\varphi(a_1) + \dots + \varphi(a_k)}{k} - \sigma \right| \ge \delta/2 \right] \le 2e^{-2(\delta/2)^2 k}. $$

This means that with a probability $\ge 1 - 2e^{-2(\delta/2)^2 k}$ the gap (19) is less than $\delta/2$. $\square$

Let us fix now a sequence $a_1, \dots, a_k \in A$, and estimate the difference in (20) as a function of random sequence $b_1, \dots, b_k \in B$. We can use once again the same argument with Hoeffding's inequality as in Claim above, now for the sampling of values of the second coordinate in $\{a_1, \dots, a_k\} \times B$. It follows that with a probability $\ge 1 - 2e^{-\delta^2 k/2}$ the gap (20) is less than $\delta/2$. Combining the bounds for (19) and (20), we obtain the lemma. $\square$

**Lemma 14.** Let $\pi$ be a two-party communication protocol where Alice and Bob access inputs $x$ and $y$ respectively, and use private random bits $r_A \in \{0, 1\}^s$ and $r_B \in \{0, 1\}^s$ respectively. For $z_1, z_2, t$ we denote by $p(x, y, z_1, z_2, t)$ the probability of the following event: given $x$ and $y$ as inputs, Alice and Bob apply the protocol $\pi$ and end up with an answer $z_1 \in \{0, 1\}^m$ for Alice, an answer $z_2 \in \{0, 1\}^m$ for Bob, and a communication transcript $t \in \{0, 1\}^l$. The probability is taken on independent and uniformly distributed $r_A, r_B$.

We apply to $\pi$ a random transformation as follows: we choose two random sequences $a_1, \dots, a_k$ and $b_1, \dots, b_k$ in $\{0, 1\}^s$. In the new communication protocol $\pi'$ Alice and Bob choose at random $i, j \in \{1, \dots, k\}$, and then apply the original communication protocol with private strings of random bits $a_i$ and $b_j$ respectively. By construction, in the protocol $\pi'$ Alice and Bob need $\log k$ private random bits each (they both need to choose a random index between 1 and $k$).

Denote by $p'(x, y, z_1, z_2, t)$ the probability analogous to $p(x, y, z_1, z_2, t)$ computed for the protocol $\pi'$. The probability is taken on the choice of independent and uniformly distributed $i, j \in \{1, \dots, k\}$. We claim that for all $x, y, z_1, z_2, t$ the probability of the event

$$ |p(x, y, z_1, z_2, t) - p'(x, y, z_1, z_2, t)| < \delta \quad (21) $$

is greater than $1 - 4e^{-\delta^2 k/2}$ (here the probability is taken over the choice of $a_1, \dots, a_k$ and $b_1, \dots, b_k$ in $\{0, 1\}^s$ in the construction of $\pi'$).

**Proof.** We apply Lemma 13 with $A = B = \{0, 1\}^s$ (the space of random bits of the original protocol), and $S = S(x, y, z_1, z_2, t)$ that consists of the pairs $(r_A, r_B) \in \{0, 1\}^s \times \{0, 1\}^s$ compatible with the given $x, y, z_1, z_2, t$. In other words, a pair $(r_A, r_B)$ belongs to $S$, if Alice and Bob given $x$ and $y$ as inputs and $r_A$ and $r_B$ as random bits, obtain with the protocol $\pi$ answers $z_1$ and $z_2$ respectively and produce a communication transcript $t$. From the lemma it follows that with the probability $1 - 4e^{-\delta^2 k/2}$, the choice of $a_1, \dots, a_k$ and $b_1, \dots, b_k$ in $\{0, 1\}^s$ in the construction of $\pi'$ provides a $\delta$-precise sampling of $S$. $\square$

Now we are ready to prove a version of Newman's theorem suitable for our setting.

**Proof of Proposition 1.** Due to Lemma 14, with randomly chosen samples $a_1, \dots, a_k$ and $b_1, \dots, b_k$ with a probability $> 1 - 4e^{-\delta^2 k/2}$ we obtain a new protocol $\pi'$ such that for each $(x, y, z_1, z_2, t)$ we have (21). We apply this construction with a $\delta$ such that

$$ \delta := \frac{\varepsilon_2}{\#\mathrm{answers}\ z_1 \cdot \#\mathrm{answers}\ z_2 \cdot \#\mathrm{transcripts}\ t} $$
and a k such that

$$4e^{-\delta^2 k/2} \cdot \#\text{inputs}(x, y) \cdot \#\text{answers} z_1 \cdot \#\text{answers} z_2 \cdot \#\text{transcripts} t < 1. \quad (22)$$

The property (22) implies that there are samples $a_1, \dots, a_k$ and $b_1, \dots, b_k$ such that (21) is true simultaneously for all $(x, y, z_1, z_2, t)$. Let us fix one such instance of sampling.

In the obtained protocol $\pi'$, for each pair of input $(x, y)$ the total probability to obtain an invalid outcome (which is the sum over all $(z_1, z_2, t)$ that are invalid) increases in comparison with the original protocol $\pi$ by at most

$$\delta \cdot \#\text{answers} z_1 \cdot \#\text{answers} z_2 \cdot \#\text{transcripts} t < \varepsilon_2. \quad (23)$$

Note that we can claim (23) even without having an explicit description of the sets of valid and invalid outcomes, it is enough to have (21) for each tuple of inputs and outcomes.

Since the length of the outputs and the communication complexity of $\pi$ are linear in $n$, the total number of inputs $(x, y)$, outputs $(z_1, z_2)$, and transcripts $t$ is $2^{O(n)}$. It is not hard to see that we can chose

$$\delta = \varepsilon_2/2^{O(n)} \quad \text{and} \quad k = 2^{O(n)}/\varepsilon_2^2$$

so that (22) and (23) are satisfied. From the choice of $k$ it follows that in the new protocol $\pi'$ Alice and Bob need only $\log k = O(n + \log(1/\varepsilon_2))$ private random bits.

It remains to notice that an appropriate instance of sampling in Lemma 14 (suitable sequences $a_1, \dots, a_k$ and $b_1, \dots, b_k$) can be found by brute-force search. To organize this search we do not need to know the precise definition of the validity of the outcome nor the class of admissible inputs $(x, y)$. Indeed, we can simulate the original protocol $\pi$ on all pairs of inputs of length $n$ and find an instance of sampling such that for each $(z_1, z_2, t)$ the probability of this outcome increases by at most $\delta$. Thus, if the original protocol was uniformly computable, so is the new one (though the computational complexity could increase dramatically). □
and a $k$ such that

$$4e^{-\delta^2 k/2} \cdot \#\text{inputs}(x, y) \cdot \#\text{answers} z_1 \cdot \#\text{answers} z_2 \cdot \#\text{transcripts} t < 1. \quad (22)$$

The property (22) implies that there are samples $a_1, \dots, a_k$ and $b_1, \dots, b_k$ such that (21) is true simultaneously for all $(x, y, z_1, z_2, t)$. Let us fix one such instance of sampling.

In the obtained protocol $\pi'$, for each pair of input $(x, y)$ the total probability to obtain an invalid outcome (which is the sum over all $(z_1, z_2, t)$ that are invalid) increases in comparison with the original protocol $\pi$ by at most

$$\delta \cdot \#\text{answers} z_1 \cdot \#\text{answers} z_2 \cdot \#\text{transcripts} t < \varepsilon_2. \quad (23)$$

Note that we can claim (23) even without having an explicit description of the sets of valid and invalid outcomes, it is enough to have (21) for each tuple of inputs and outcomes.

Since the length of the outputs and the communication complexity of $\pi$ are linear in $n$, the total number of inputs $(x, y)$, outputs $(z_1, z_2)$, and transcripts $t$ is $2^{O(n)}$. It is not hard to see that we can chose

$$\delta = \varepsilon_2/2^{O(n)} \quad \text{and} \quad k = 2^{O(n)}/\varepsilon_2^2$$

so that (22) and (23) are satisfied. From the choice of $k$ it follows that in the new protocol $\pi'$ Alice and Bob need only $\log k = O(n + \log(1/\varepsilon_2))$ private random bits.

It remains to notice that an appropriate instance of sampling in Lemma 14 (suitable sequences $a_1, \dots, a_k$ and $b_1, \dots, b_k$) can be found by brute-force search. To organize this search we do not need to know the precise definition of the validity of the outcome nor the class of admissible inputs $(x, y)$. Indeed, we can simulate the original protocol $\pi$ on all pairs of inputs of length $n$ and find an instance of sampling such that for each $(z_1, z_2, t)$ the probability of this outcome increases by at most $\delta$. Thus, if the original protocol was uniformly computable, so is the new one (though the computational complexity could increase dramatically). $\square$