Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1412.4904 · Leibniz international proceedings in informatics

New Bounds for the Garden-Hose Model

Hartmut Klauck, Supartha Podder

Published Jan 1, 2014• 6 citations
arXivHTMLPDF

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\cdot \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 $Ω(n^{2+ε})$ 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.

DOI
10.4230/lipics.fsttcs.2014.481

Related papers

Communication Memento: Memoryless Communication Complexity

Srinivasan Arunachalam, Supartha Podder

We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].

Conference on Innovations in Theoretical Computer Science•Jan 1, 2021•1 citation

Communication Memento: Memoryless Communication Complexity

Srinivasan Arunachalam, Supartha Podder

We study the communication complexity of computing functions $F:\{0,1\}^n\times \{0,1\}^n \rightarrow \{0,1\}$ in the memoryless communication model. Here, Alice is given $x\in \{0,1\}^n$, Bob is given $y\in \{0,1\}^n$ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x; the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study space-bounded communication models. We establish the following: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose complexity; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c>1 for which the memoryless communication complexity is at least $c \log n$? Note that $c\geq 2+\varepsilon$ would imply a $Ω(n^{2+\varepsilon})$ lower bound for general formula size, improving upon the best lower bound by Nečiporuk in 1966.

arXiv:2005.04068•Leibniz international proceedings in informatics•May 8, 2020•0 citations

The garden-hose model

Harry Buhrman, Serge Fehr, Christian Schaffner +1 more

We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function f:{0,1}n x {0,1}n -> {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x ∈ {0,1}n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y ∈ {0,1}n. Alice turns on the water tap that she also connected to one of the pipes. Then, the water comes out on Alice's or Bob's side depending on the function value f(x,y).

arXiv:1109.2563•Conference on Innovations in Theoretical Computer Science•Jan 3, 2013•27 citations

On the riddle of coding equality function in the garden hose model

Oded Margalit

Recently, Harry Buhrman et al introduced a novel communication complexity model, called “garden-hose”. This model sprout from a research on using quantum properties to allow for position based cryptography. SAT is one of the fundamental NP-Complete problem - finding a satisfying assignment to a CNF (conjunctive Normal Form) formula, or proving that none exists. We will not get into the details of the quantum physics, neither we are going to explain the internal work of SAT solver. Instead we will start from the mathematical garden hose model; describe the way we used SAT solver as a tool; give some lower and upper bounds on implementing the equality function; and conclude with open questions.

Information Theory and Applications Workshop (ITA)•Feb 1, 2014•3 citations

Lower Bounds on Quantum Multiparty Communication Complexity

Troy Lee, Gideon Schechtman, Adi Shraibman

A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•21 citations

New strong direct product results in communication complexity.

Rahul Jain

We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and e > 0 be a constant. Let R1,pube(f) represent the communication complexity of f, with worst-case error e in this model. We show that if for computing fk (k independent copies of f) in this model, o(k c R1, pub1/3(f)) communication is used, then the success is exponentially small in k. We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest.Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω(n) for the set-disjointness problem on n-bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.

Electronic colloquium on computational complexity•Jan 1, 2011•16 citations
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)Θ(n)Θ(n) bounds for Inner Product mod 2 and Disjointness), as well as an O(n⋅log⁡3n)O(n\cdot \log^3 n)O(n⋅log3n) 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)GH(f)GH(f) of the order Ω(n2+ε)Ω(n^{2+ε})Ω(n2+ε) 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.
We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].
We study the communication complexity of computing functions F:{0,1}n×{0,1}n→{0,1}F:\{0,1\}^n\times \{0,1\}^n \rightarrow \{0,1\}F:{0,1}n×{0,1}n→{0,1} in the memoryless communication model. Here, Alice is given x∈{0,1}nx\in \{0,1\}^nx∈{0,1}n, Bob is given y∈{0,1}ny\in \{0,1\}^ny∈{0,1}n and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x; the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study space-bounded communication models. We establish the following: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose complexity; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c>1 for which the memoryless communication complexity is at least clog⁡nc \log nclogn? Note that c≥2+εc\geq 2+\varepsilonc≥2+ε would imply a Ω(n2+ε)Ω(n^{2+\varepsilon})Ω(n2+ε) lower bound for general formula size, improving upon the best lower bound by Nečiporuk in 1966.
We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function f:{0,1}n x {0,1}n -> {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x ∈ {0,1}n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y ∈ {0,1}n. Alice turns on the water tap that she also connected to one of the pipes. Then, the water comes out on Alice's or Bob's side depending on the function value f(x,y).
Recently, Harry Buhrman et al introduced a novel communication complexity model, called “garden-hose”. This model sprout from a research on using quantum properties to allow for position based cryptography. SAT is one of the fundamental NP-Complete problem - finding a satisfying assignment to a CNF (conjunctive Normal Form) formula, or proving that none exists. We will not get into the details of the quantum physics, neither we are going to explain the internal work of SAT solver. Instead we will start from the mathematical garden hose model; describe the way we used SAT solver as a tool; give some lower and upper bounds on implementing the equality function; and conclude with open questions.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.
We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and e > 0 be a constant. Let R1,pube(f) represent the communication complexity of f, with worst-case error e in this model. We show that if for computing fk (k independent copies of f) in this model, o(k c R1, pub1/3(f)) communication is used, then the success is exponentially small in k. We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest.Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω(n) for the set-disjointness problem on n-bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.