2026-07-19T23:09:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:607 2024-03-06T11:06:45Z ddc:004 open_access

Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity Ford, Jeff Gál, Anna Multiparty communication complexity lower bounds 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 $Omega(n/2^k)$ multiparty communication complexity. We also exhibit constructions of Hadamard tensors, giving $Omega(n/2^k)$ lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff Ford and Anna Gál 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06111.9 urn:nbn:de:0030-drops-6076 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.9 eng https://creativecommons.org/licenses/by/4.0/legalcode