2005 | OriginalPaper | Buchkapitel
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity
verfasst von : Jeff Ford, Anna Gál
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 analogue 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, giving Ω(
n
/2
k
) lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions.