We introduce a new information-theoretic complexity measure @math for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity ( @math ) and logarithm of partition complexity ( @math ), which have so far appeared conceptually quite different from each other. @math is an external information complexity measure based on R 'enyi mutual information of order infinity. In the definition of @math , relaxing the order of R 'enyi mutual information from infinity to 1 yields @math , while @math is obtained by replacing protocol transcripts with what we term "pseudotranscripts," which omits the interactive nature of a protocol, but only requires that the probability of any transcript given the inputs @math and @math to the two parties, factorizes into two terms which depend on @math and @math separately. Further understanding @math might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity. We also show that applying both the above relaxations simultaneously to @math gives a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than , using an arguably more direct proof.
 This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function @math with respect to a distribution @math is @math , then any two party randomized protocol computing @math must reveal at least @math bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on @math must reveal @math bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is @math , which provides an alternative proof to the recent proof of Viola Viola11 of the @math lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight @math lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a very recent breakthrough work of kerenidis2012lower , this simulation procedure was the main building block for proving that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity. We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold. Three decades of research in communication complexity have led to the invention of a number of techniques to lower bound randomized communication complexity. The majority of these techniques involve properties of large submatrices (rectangles) of the truth-table matrix defining a communication problem. The only technique that does not quite fit is information complexity, which has been investigated over the last decade. Here, we connect information complexity to one of the most powerful "rectangular" techniques: the recently-introduced smooth corruption (or "smooth rectangle") bound. We show that the former subsumes the latter under rectangular input distributions. We conjecture that this subsumption holds more generally, under arbitrary distributions, which would resolve the long-standing direct sum question for randomized communication. As an application, we obtain an optimal @math lower bound on the information complexity---under the uniform distribution ---of the so-called orthogonality problem (ORT), which is in turn closely related to the much-studied Gap-Hamming-Distance (GHD). The proof of this bound is along the lines of recent communication lower bounds for GHD, but we encounter a surprising amount of additional technical detail.  Let M e 0, 1, 2, ..., m —1 , N e 0, 1, 2,..., n —1 , and f:M × N → 0, 1 a Boolean-valued function. We will be interested in the following problem and its related questions. Let i e M , j e N be integers known only to two persons P 1 and P 2 , respectively. For P 1 and P 2 to determine cooperatively the value f ( i, j ), they send information to each other alternately, one bit at a time, according to some algorithm. The quantity of interest, which measures the information exchange necessary for computing f , is the minimum number of bits exchanged in any algorithm. For example, if f ( i, j ) e ( i + j ) mod 2. then 1 bit of information (conveying whether i is odd) sent from P 1 to P 2 will enable P 2 to determine f ( i, j ), and this is clearly the best possible. The above problem is a variation of a model of Abelson [1] concerning information transfer in distributive computions. Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. We study this question in the simultaneous message (SM) model of communication introduced by A.C. Yao (1979). The equality problem for n-bit strings is well known to have SM complexity spl Theta ( spl radic n). We prove that solving m copies of the problem has complexity spl Omega (m spl radic n); the best lower bound provable using previously known techniques is spl Omega ( spl radic (mn)). We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalized to a broader class of functions. We introduce a new notion of informational complexity which is related to SM complexity and has nice direct sum properties. This notion is used as a tool to prove the above results; it appears to be quite powerful and may be of independent interest. We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck [Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity, 2010, pp. 247--258] and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm-based methods (e.g., the @math method) and rectangle-based methods (e.g., the rectangle corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols, where the players can either output a value or abort. We prove, using a sampling protocol designed by Braverman and Weinstein [in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 7408, Springer, Heidelberg, 2012, pp. 459--470], the following compression l... We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman. Previously, only a separation of communication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity ≤ O(k), with respect to any input distribution, and distributional communication complexity ≥ 2k, with respect to some input distribution. In particular, this shows that a communication protocol cannot always be compressed to its external information. By a result of Braverman, our gap is the largest possible. Moreover, since the upper bound of O(k) on the external information complexity of the problem is obtained with respect to any input distribution, our result implies an exponential gap between communication complexity and information complexity (both internal and external) in the non-distributional setting of Braverman. In this setting, no gap was previously known, even for internal information complexity.   We present a new method for proving strong lower bounds in communication complexity. This method is based on the notion of the conditional information complexity, of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving conditional information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations.Our paradigm leads to two main results: (1) An improved lower bound for the multi-party set-disjointness problem in the general communication complexity model, and a nearly optimal lower bound in the one-way communication model. As a consequence, we show that for any real k > 2, approximating the kth frequency moment in the data stream model requires essentially Ω(n1-2 k) space; this resolves a conjecture of (J. Comput. System Sci. 58(1) (1999) 137).(2) A lower bound for the Lp approximation problem in the general communication model: this solves an open problem of Saks and Sun (in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 360-369). As a consequence, we show that for p > 2, approximating the Lp norm to within a factor of ne in the data stream model with constant number of passes requires Ω(n1-4e-2 p) space. We prove three different types of complexity lower bounds for the one-way unbounded-error and bounded-error error probabilistic communication protocols for boolean functions. The lower bounds are proved in terms of the deterministic communication complexity of functions and in terms of the notion “probabilistic communication characteristic” that we define. We present boolean functions with the different probabilistic communication characteristics which demonstrates that each of these lower bounds can be more precise than the others depending on the probabilistic communication characteristics of a function. Our lower bounds are good enough for proving that proper hierarchy for one-way probabilistic communication complexity classes depends on a measure of bounded error. As the application of lower bounds for probabilistic communication complexity, we prove two different types of complexity lower bounds for the one-way bounded-error error probabilistic space complexity. Our lower bounds are good enough for proving proper hierarchies for different one-way probabilistic space communication complexity classes inside SPACE(n) (namely for bounded error probabilistic computation, and for errors of probabilistic computation). We show the following new lower bounds in two concrete complexity models: (1) In the two-party communication complexity model, we show that the tribes function on n inputs[6] has two-sided error randomized complexity Ω(n), while its nondeterminstic complexity and co-nondeterministic complexity are both Θ(√n). This separation between randomized and nondeterministic complexity is the best possible and it settles an open problem in Kushilevitz and Nisan[17], which was also posed by Beame and Lawry[5]. (2) In the Boolean decision tree model, we show that the recursive majority-of-three function on 3h inputs has randomized complexity Ω((7 3)h). The deterministic complexity of this function is Θ(3h), and the nondeterministic complexity is Θ(2h). Our lower bound on the randomized complexity is a substantial improvement over any lower bound for this problem that can be obtained via the techniques of Saks and Wigderson [23], Heiman and Wigderson[14], and Heiman, Newman, and Wigderson[13]. Recursive majority is an important function for which a class of natural algorithms known as directional algorithms does not achieve the best randomized decision tree upper bound. These lower bounds are obtained using generalizations of information complexity, which quantifies the minimum amount of information that will have to be revealed about the inputs by every correct algorithm in a given model of computation. The primary goal of this paper is to define and study the interactive information complexity of functions. Let f(x,y) be a function, and suppose Alice is given x and Bob is given y. Informally, the interactive information complexity IC(f) of f is the least amount of information Alice and Bob need to reveal to each other to compute f. Previously, information complexity has been defined with respect to a prior distribution on the input pairs (x,y). Our first goal is to give a definition that is independent of the prior distribution. We show that several possible definitions are essentially equivalent. We establish some basic properties of the interactive information complexity IC(f). In particular, we show that IC(f) is equal to the amortized (randomized) communication complexity of f. We also show a direct sum theorem for IC(f) and give the first general connection between information complexity and (non-amortized) communication complexity. This connection implies that a non-trivial exchange of information is required when solving problems that have non-trivial communication complexity. We explore the information complexity of two specific problems - Equality and Disjointness. We show that only a constant amount of information needs to be exchanged when solving Equality with no errors, while solving Disjointness with a constant error probability requires the parties to reveal a linear amount of information to each other.    We describe new ways to simulate two-party communication protocols to get protocols with potentially less communication. We show that every communication protocol that communicates @math bits and reveals @math bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most @math bits of communication. If the protocol reveals @math bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with @math bits of communication. These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst-case computation, computing @math copies of a function requires @math times the communication required for computing one copy of the function. For average case complexity, given any distribution @math on inputs, computing @math copies of the function on @math inputs sampled independently according...