The Garden-Hose Model
Supartha Podder, University of Ottawa
In 2011 Harry Buhrman, Serge Fehr, Christian Schaffner and Florian Speelman proposed a new measure of complexity for finite Boolean functions, called "The Garden-hose complexity". This measure can be viewed as a type of distributed space complexity where two players with private inputs compute a Boolean function co-operatively. While its motivation mainly came from the applications to position based quantum cryptography, the playful definition of the model is quite appealing in itself.