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.