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.
The partition bound was developed in @cite_5 , and has subsumed a long line of combinatorial bounds @cite_2 (see e.g., @cite_5 @cite_0 ). The relaxed partition bound put forth in @cite_7 , similarly subsumes several combinatorial bounds, with the exception of the partition bound itself.
@cite_0 @cite_5 @cite_7 @cite_2
2952015701 2571088576 2205230658
We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle corruption bound and the generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate polynomial degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than polynomial degree and classical adversary bounds. 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... Consider a two-party quantum communication protocol for computing some function f : 0, 1 sup n spl times 0, 1 sup n spl rarr Z. We show that the first message of P can be compressed to 0(k) classical bits using prior entanglement if it carries at most k bits of information about the sender's input. This implies a general direct sum result for one-round and simultaneous quantum protocols. It also implies a new round elimination lemma in quantum communication, which allows us to extend recent classical lower bounds on the cell probe complexity of some data structure problems, e.g. approximate nearest neighbor searching on the Hamming cube 0, 1 sup n , to the quantum setting. We then show an optimal tradeoff between the privacy losses of Alice and Bob in computing f in terms of the one-round quantum communication complexity of f with prior entanglement. This tradeoff is independent of the number of rounds of communication. The above message compression and privacy tradeoff results use a lot of qubits of prior entanglement, leading one to wonder how much prior entanglement is really required by a quantum protocol. We show that Newman's [1991] technique of reducing the number of public coins in a classical protocol cannot be lifted to the quantum setting. We do this by defining a general notion of black-box reduction of prior entanglement that subsumes Newman's technique. Intuitively, a black-box reduction does not change the unitary transforms of Alice and Bob; it only decreases the amount of entanglement of the prior entangled state. We prove that such a black-box reduction is impossible for quantum protocols by exhibiting a particular one-round quantum protocol for the equality function where the black-box technique fails to reduce the amount of prior entanglement by more than a constant factor.