1 Search Results for "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-dev.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}
}

Refine by Author
1 Ford, Jeff
1 Gál, Anna

Refine by Classification

Refine by Keyword
1 Multiparty communication complexity
1 lower bounds

Refine by Type
1 document

Refine by Publication Year
1 2006

1 Search Results for "Ford, Jeff"

Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message