Abstract:

Title: Quantum Weak Coin Flipping with Arbitrarily Small Bias

Abstract: “God does not play dice. He flips coins instead.” In weak coin flipping, Alice and Bob each have a priori a desired coin outcome. The outcomes can be labeled as “Alice wins” and “Bob wins”, and we do not care if the players cheat in order to increase their own probability of losing. Kitaev’s (2004) second coin-flipping formalism can be used to relate coin flipping (and many other quantum games) to the theory of convex cones and operator monotone functions. Mochon (2007) used the formalism to build a toolchain of transitions and finally translated the weak coin-flipping into Time Independent Point Games which involves real value functions with finite support. And found that for every integer k≥0 we could build a protocol with P^*_A = P^*_B = (k+1)/(2k+1), and the limit (k → ∞) achieves arbitrarily small bias to 1/2.

Title: The Gaussian Noise Sensitivity of Degree-d Polynomial Threshold Functions

Abstract: The noise sensitivity is has been studied in a range of contexts including Boolean function analysis, percolation theory. I will introduce the relation between computational learning theory and gaussian noise sensitivity. After that, the upper bound of a degree-d polynomial threshold function will be presented based on the work of Daniel M. Kane.

Title: Quantum Private Queries

Abstract: Private queries allow a user Alice to learn an element of a database held by a provider Bob without revealing which element she was interested in, while limiting her information about the other elements. In my talk, I will present two quantum schemes to deal with this symmetrically private information problem. One is a simple cheat sensitive quantum protocol, proposed by Giovannetti, Lloyd and Maccone. The other is based on a quantum key distribution protocol (QKD), proposed by Markus Jakobi et al. I hope that from my talk, you can feel the power of quantum mechanics.