文章基本信息

标题：New Bounds for the Garden-Hose Model
本地全文：下载
作者：Hartmut Klauck ; Supartha Podder
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：29
页码：481-492
DOI：10.4230/LIPIcs.FSTTCS.2014.481
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Space Complexity; Communication Complexity; Garden-Hose Model