@inproceedings{45ad5427f30d492a834843663f2345d0,
title = "New bounds for the garden-hose model",
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 θ(n) bounds for Inner Product mod 2 and Disjointness), as well as an O(n·log3 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 Ω(n2+ε) will be hard to obtain for explicit functions. Furthermore we study a timebounded variant of the model, in which even modest savings in time can lead to exponential lower bounds on the size of garden-hose protocols.",
keywords = "Communication complexity, Garden-hose model, Space complexity",
author = "Hartmut Klauck and Supartha Podder",
year = "2014",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.FSTTCS.2014.481",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "481--492",
editor = "Venkatesh Raman and Suresh, \{S. P.\}",
booktitle = "34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014",
note = "34th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2014 ; Conference date: 15-12-2014 Through 17-12-2014",
}