Lower bound methods for multiparty communication complexity

dc.contributor.advisorGál, A. (Anna)en
dc.creatorFord, Jeffrey Stephenen
dc.description.abstractMultiparty 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.
dc.description.departmentComputer Science
dc.rightsCopyright is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works.en
dc.subject.lcshCombinatorial analysisen
dc.subject.lcshTensor productsen
dc.subject.lcshComputational complexityen
dc.titleLower bound methods for multiparty communication complexityen
thesis.degree.departmentComputer Sciencesen
thesis.degree.disciplineComputer Sciencesen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.nameDoctor of Philosophyen

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
574.58 KB
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
1.65 KB
Plain Text