Please use this identifier to cite or link to this item:
Title: New bounds for the garden-hose model
Authors: Klauck, Hartmut
Podder, Supartha
Keywords: Space Complexity
Communication Complexity
Issue Date: 2014
Source: Klauck, H., & Podder, S. (2014). New bounds for the garden-hose model. LIPIcs–Leibniz International Proceedings in Informatics, 481-492. doi:10.4230/LIPIcs.FSTTCS.2014.481
Series/Report no.: LIPIcs–Leibniz International Proceedings in Informatics
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.
Rights: © 2014 The Author(s) (Leibniz International Proceedings in Informatics). Licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
New Bounds for the Garden-Hose Model.pdf458.74 kBAdobe PDFThumbnail

Google ScholarTM



Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.