DagSemProc.06111.9.pdf
- Filesize: 215 kB
- 20 pages
Document
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6111
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-10-09
Cite AsGet BibTex
Jeff Ford and Anna Gál. Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06111.9
https://doi.org/10.4230/DagSemProc.06111.9
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 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.
Keywords
- Multiparty communication complexity
- lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads