20130101
The GardenHose Model
Publication
Publication
Presented at the
Innovations in Theoretical Computer Science
We define a new model of communication complexity, called the gardenhose model. Informally, the gardenhose 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).
We prove almostlinear lower bounds on the gardenhose complexity for concrete functions like inner product, majority, and equality, and we show the existence of functions with exponential gardenhose complexity. Furthermore, we show a connection to classical complexity theory by proving that all functions computable in logspace have polynomial gardenhose complexity.
We consider a randomized variant of the gardenhose complexity, where Alice and Bob hold preshared randomness, and a quantum variant, where Alice and Bob hold preshared quantum entanglement, and we show that the randomized gardenhose complexity is within a polynomial factor of the deterministic gardenhose complexity. Examples of (partial) functions are given where the quantum gardenhose complexity is logarithmic in n while the classical gardenhose complexity can be lower bounded by nc for constant c>0.
Finally, we show an interesting connection between the gardenhose model and the (in)security of a certain class of quantum positionverification schemes.
Additional Metadata  

MSC  Algorithms; complexity (msc 11Y16), Cryptography (msc 94A60) 
THEME  Information (theme 2) 
Editor  R. Kleinberg 
Project  Quantum Cryptography 
Conference  Innovations in Theoretical Computer Science 
Citation 
Buhrman, H.M, Fehr, S, Schaffner, C, & Speelman, F. (2013). The GardenHose Model. In R Kleinberg (Ed.), .
