The question of how much communication is required between collaborating parties to compute a function of their data is of fundamental importance in the fields of theoretical computer science and information theory. In this work, the focus is on coming up with lower bounds on this. The information cost of a protocol is the amount of information the protocol reveals to Alice and Bob about each others inputs, and the information complexity of a function is the infimum of information costs over all valid protocols. For the amortized case, it is known that the optimal rate for the computation is equal to the information complexity. Exactly computing this information complexity is not straight forward however. In this work we lower bound information complexity for independent inputs in terms of the Wyner common information of a certain pair of random variables. We show a structural property for the optimal auxiliary random variable of Wyner common information and exploit this to exactly compute the Wyner common information in certain cases. The lower bound obtained through this technique is shown to be tight for a non-trivial example - equality (EQ) for the ternary alphabet. We also give an example to show that the lower bound may, in general, not be tight.
The question of how much communication is required between collaborating parties to compute a function of their data is of fundamental importance in the fields of theoretical computer science and information theory. In this work, the focus is on coming up with lower bounds on this. The information cost of a protocol is the amount of information the protocol reveals to Alice and Bob about each others inputs, and the information complexity of a function is the infimum of information costs over all valid protocols. For the amortized case, it is known that the optimal rate for the computation is equal to the information complexity. Exactly computing this information complexity is not straight forward however. In this work we lower bound information complexity for independent inputs in terms of the Wyner common information of a certain pair of random variables. We show a structural property for the optimal auxiliary random variable of Wyner common information and exploit this to exactly compute the Wyner common information in certain cases. The lower bound obtained through this technique is shown to be tight for a non-trivial example - equality (EQ) for the ternary alphabet. We also give an example to show that the lower bound may, in general, not be tight.
In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.
A simulation of an interactive protocol entails the use of interactive communication to produce the output of the protocol to within a fixed statistical distance epsilon. Recent works have proposed that the information complexity of the protocol plays a central role in characterizing the minimum number of bits that the parties must exchange for a successful simulation, namely the distributional communication complexity of simulating the protocol. Several simulation protocols have been proposed with communication complexity depending on the information complexity of the simulated protocol. However, in the absence of any general lower bounds for distributional communication complexity, the conjectured central role of information complexity is far from settled. We fill this gap and show that the distributional communication complexity of epsilon-simulating a protocol is bounded below by the epsilon-tail lambda(epsilon) of the information complexity density, a random variable with information complexity as its expected value. For protocols with bounded number of rounds, we give a simulation protocol that yields a matching upper bound. Thus, it is not information complexity but lambda(epsilon), that governs the distributional communication complexity. As applications of our bounds, in the amortized regime for product protocols, we identify the exact second order term, together with the precise dependence on epsilon. For general protocols such as a mixture of two product protocols or for the amortized case when the repetitions are not independent, we derive a general formula for the leading asymptotic term. These results sharpen and significantly extend known results in the amortized regime. In the single-shot regime, our lower bound sheds light on the dependence of communication complexity on epsilon. We illustrate this with an example that exhibits an arbitrary separation between distributional communication complexity and information complexity for all sufficiently small epsilon.
Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x,y). That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value f(x,y), and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1≤g(n)≤2⋅(2n−1) there are functions that can be privately computed with g(n)-rounds of communication, but not with (g(n)−1)-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions p and q over domains X and Y, respectively. Their goal is to estimate Ex∼p,y∼q[f(x,y)] to within additive error ε for a bounded function f, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of f and the error parameter ε. The random sampling approach -- estimating the mean by averaging f over O(1/ε2) random samples -- requires O(R(f)/ε2) total communication, where R(f) is the randomized communication complexity of f. We design a new debiasing protocol which improves the dependence on 1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.