License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.481
URN: urn:nbn:de:0030-drops-48657
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4865/
Go to the corresponding LIPIcs Volume Portal

Klauck, Hartmut ; Podder, Supartha

New Bounds for the Garden-Hose Model

pdf-format:
41.pdf (0.4 MB)

Abstract

We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown Theta(n) bounds for Inner Product mod 2 and Disjointness), as well as an O(n * log^3(n) upper bound for the Distributed Majority function (previously conjectured to have quadratic complexity). We show an efficient simulation of formulae made of AND, OR, XOR gates in the garden-hose model, which implies that lower bounds on the garden-hose complexity GH(f) of the order Omega(n^{2+epsilon}) will be hard to obtain for explicit functions. Furthermore we study a time-bounded variant of the model, in which even modest savings in time can lead to exponential lower bounds on the size of garden-hose protocols.

BibTeX - Entry

@InProceedings{klauck_et_al:LIPIcs:2014:4865,
  author =	{Hartmut Klauck and Supartha Podder},
  title =	{{New Bounds for the Garden-Hose Model}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{481--492},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4865},
  URN =		{urn:nbn:de:0030-drops-48657},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.481},
  annote =	{Keywords: Space Complexity, Communication Complexity, Garden-Hose Model}
}

Keywords: Space Complexity, Communication Complexity, Garden-Hose Model
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI