### Book chapter

## Making Randomness Public in Unbounded-Round Information Complexity

### In book

In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X, Bob receives a value of another random variable Y that is jointly distributed with X. Alice’s goal is to transmit X to Bob (with some error probability εε). Instead of one-way transmission we allow them to interact. They may also use shared randomness.

Newman's theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new direct sum theorems through the compression of interactive communication in the bounded-round setting. Furthermore, we show that if a Reverse Newman's Theorem can be proven in full generality, then full compression of interactive communication and fully-general direct-sum theorems will result.

We initiate a comprehensive study of the complexity of computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains (as opposed to domains such as $\zon$ or $\mon$ that enforce multilinearity). A typical example of such a general Boolean domain, for the purpose of our results, is $\{1,2\}^n$. We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest. First we motivate the study of PTFs over the $\{1,2\}^n$ domain by showing their close relation to depth two threshold circuits. In particular we show that PTFs of polynomial length and polynomial degree compute exactly the functions computed by polynomial size $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf MAJ}}$ circuits. We note that known lower bounds for $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf MAJ}}$ circuits extends to the likely strictly stronger model of PTFs (with no degree restriction). We also show that a ``max-plus'' version of PTFs are related to $\mathsf{AC}^0 \circ \ensuremath{{\rm \sf THR}}$ circuits. We exploit this connection to gain a better understanding of threshold circuits. In particular, we show that (super-logarithmic) lower bounds for 3-player randomized communication protocols with unbounded error would yield (super-polynomial) size lower bounds for $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf THR}}$ circuits. Finally, having thus motivated the model, we initiate structural studies of PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length.

A Euclidean distance matrix D(α) is defined by D_ij=(α_i−α_j)^2, where α=(α_1,…,α_n) is a real vector. We prove that D(α) cannot be written as a sum of [2sqrt(n)−2] nonnegative rank-one matrices, provided that the coordinates of α are algebraically independent. As a corollary, we provide an asymptotically optimal separation between the complexities of quantum and classical communication protocols computing a given matrix in expectation.

This book constitutes the refereed proceedings of the First International Conference on Data Compression, Communications and Processing held in Palinuro, Italy, in June 2011.

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha- y gin. Randomized Individual Communication Complexity. IEEE Con- ference on Computational Complexity 2008: 321-331] considered com- munication complexity of the following problem. Alice has a bi- nary string x and Bob a binary string y, both of length n, and they want to compute or approximate Kolmogorov complexity C(x|y) of x conditional to y. It is easy to show that deterministic communica- tion complexity of approximating C(x|y) with precision α is at least n − 2α − O(1). The above referenced paper asks what is random- ized communication complexity of this problem and shows that for r- round randomized protocols its communication complexity is at least Ω((n/α)1/r ). In this paper, for some positive ε, we show the lower bound 0.99n for (worst case) communication length of any random- ized protocol that with probability at least 0.01 approximates C(x|y) with precision εn for all input pairs.