The Garden-Hose Model

par

Supartha Podder

Université d'Ottawa

Jeudi 22 novembre, 15:30-16:30, Salle 3195, Pavillon André-Aisenstadt

Université de Montréal, 2920 Chemin de la Tour

Café avant 15:00-15:30

La conférence sera présentée en anglais.

Résumé:

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 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.