[QIP-Sem] QIP seminar, Fri 11/9, 2:00 PM, 6C-442, Mario Szegedy

[Peter Shor]

MIT Quantum Information Processing seminar
Friday 11/9 at 2:00 PM in 6C-442
-------------------------------------------------

Mario Szegedy (Rutgers)

Symmetric Garden Hose Constructions

Abstract:

The Garden Hose complexity is a new communication complexity introduced by H. Buhrman, S. Fehr, C. Schaffner and F. Speelman 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 Buhrman at all. With the help of of a new approach and of our handmade simulated annealing based solver, we have out-performed the commercial set solvers used by Buhrman at all. 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 farther, although several interesting open problems remain. In our talk we explain the background, our algorithmic efforts, and  give a pictorial presentation of the symmetries.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem