11:30, Seminar Hall
Garden-Hose Model
Supartha Podder
U. Texas, Austin.
27-10-17

---

Abstract

Recently, Buhrman et al. 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 is mainly in 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.