1 Search Results for "Ford, Jeff"

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)

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

  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}
  • 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

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail