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
2571088576 2952015701 2104886711 2070232376
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 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 and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the ?2 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 the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2^ -O(I) and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n^ 1 3 ), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem. Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [Bui and Jones, Proc. of the 6th SIAM Conference on Parallel Processing for Scientific Computing, 1993, 445--452; Hendrickson and Leland, A Multilevel Algorithm for Partitioning Graphs, Tech. report SAND 93-1301, Sandia National Laboratories, Albuquerque, NM, 1993]. From the early work it was clear that multilevel techniques held great promise; however, it was not known if they can be made to consistently produce high quality partitions for graphs arising in a wide range of application domains. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme produces partitions that are consistently better than those produced by spectral partitioning schemes in substantially smaller time. Also, when our scheme is used to compute fill-reducing orderings for sparse matrices, it produces orderings that have substantially smaller fill than the widely used multiple minimum degree algorithm.