Lower bound methods for multiparty communication complexity

Multiparty communication complexity is a measure of the amount of communication required to compute a function whose input is distributed among multiple parties. Proving lower bounds in the “Number on the Forehead” model of Chandra, Furst, and Lipton has been quite difficult, but results are of importance in many areas including time-space tradeoffs and lower bounds for VLSI and Boolean circuits, as well as constructions of universal traversal sequences and pseudorandom generators for space bounded computation. Currently, the largest known lower bounds for explicit functions are of the form Ω(n/2 k ), where k is the number of players and n is the number of bits missed by each player. All of the previous lower bounds of this type utilize some version of the discrepancy method, thus they also apply to vii the distributional and randomized multiparty communication complexity models. We introduce three new measures, tensor weight, tensor norm, and tensor rank, each of which can be used to prove lower bounds on multiparty communication complexity. We prove that the discrepancy of a multidimensional tensor can be estimated using the weight of the tensor. This measure appears to be simpler to analyze and it gives close to optimal bounds on discrepancy. Our second measure, the norm, can be used to estimate the weight, and thus discrepancy. We show an interesting connection between tensor norm and Lagrange multipliers. The tensor rank method is not based on the discrepancy method. We also give a variant of tensor rank that provides lower bounds on probabilistic communication complexity. We give an extension of the Hadamard property of matrices for tensors in multiple dimensions, and we present an Ω(n/2 k ) lower bound on any k-party, n-bit communication problem represented by a Hadamard tensor. We also give explicit constructions of Hadamard tensors giving Ω(n/2 k ) lower bounds for a new class of Boolean functions. We also examine all functions previously known to have Ω(n/ck ) lower bounds and show their place in a unifying framework of nearly Hadamard tensors.