The Garden-Hose Model

Wednesday, April 17, 2019 11:00 am - 11:00 am EDT (GMT -04:00)

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.

Recently there has been some work proving non-trivial upper bounds for functions like Equality, Majority, etc., in this model and establishing new connections of this model with well studied models like communication complexity, permutation branching programs, and formula size.

In this talk we will discuss these results and look at potential directions for future research.

Relevant papers: 
https://arxiv.org/abs/1109.2563
https://arxiv.org/abs/1412.4904
https://arxiv.org/abs/1510.06120
https://arxiv.org/abs/1708.09156


About the speaker

Supartha Podder is a postdoctoral researcher with Anne Broadbent at the University of Ottawa. Previously, he was a postdoctoral fellow with Scott Aaronson at the University of Texas at Austin. He received his PhD in computer science from the Centre for Quantum Technologies, National University of Singapore, under the supervision of Hartmut Klauck.