Event

Supartha Podde (Université d'Ottawa)

Thursday, November 22, 2018 15:30to16:30
Room 3195, Pav. André-Aisenstadt, CA

The Garden-Hose Model

Café et biscuits à partir de 15 h.

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.

Follow us on

Back to top