Search Results

Documents authored by Ford, Jeff


Document
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity

Authors: Jeff Ford and Anna Gál

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{ford_et_al:DagSemProc.06111.9,
  author =	{Ford, Jeff and G\'{a}l, Anna},
  title =	{{Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.9},
  URN =		{urn:nbn:de:0030-drops-6076},
  doi =		{10.4230/DagSemProc.06111.9},
  annote =	{Keywords: Multiparty communication complexity, lower bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail