Skip to content Skip to navigation
Qualifying Exam
9/27/2013 02:15 pm
CoRE B (Room 305)

The Garden Hose Complexity for Equality Function

Yixin Xu, Rutgers University

Examination Committee: Prof. Mario Szegedy (chair), Prof. Alex Borgida, Prof. Swastik Kopparty and Prof. Michael Saks

Abstract

The garden hose complexity is a new communication complex- ity introduced by H. Buhrman, S. Fehr, C. Scha?ner and F. Speel- man [BFSS13] to analyze position-based cryptography protocols in the quantum setting. We focus on the garden hose complexity of the equality function, and improve on the bounds of O. Margalit and A. Matsliah[MM12]. With the help of a new approach and of our hand- made simulated annealing based solver, we have out-performed the IBM SAT-Solver used by Margalit and Matsliah. We have also found beautiful symmetries of the solutions that have lead us to develop the notion of garden hose permutation groups. Then, exploiting this new concept, we get even further, although several interesting open problems remain.