Hadamard tensors and lower bounds on multiparty communication complexity |
| |
Authors: | Jeff Ford Anna Gál |
| |
Affiliation: | 1. Microsoft, Redmond, WA, 98052-6399, USA 2. Department of Computer Science, University of Texas at Austin, Austin, TX, 78712-1188, USA
|
| |
Abstract: | We develop a new method for estimating the discrepancy of tensors associated with multiparty communication problems in the “Number on the Forehead” model of Chandra, Furst, and Lipton. We define an analog of the Hadamard property of matrices for tensors in multiple dimensions and show that any k-party communication problem represented by a Hadamard tensor must have Ω(n/2 k ) multiparty communication complexity. We also exhibit constructions of Hadamard tensors. This allows us to obtain Ω(n/2 k ) lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|