Spring 2014

Direct Products and Parallel Repetition

Thursday, Feb. 27, 2014 2:00 pm3:00 pm PST

Add to Calendar


Calvin Lab Auditorium

Direct products arise in many complexity settings, often for the purpose of hardness amplification.

One particular setting is that of two-prover games, whose direct product is called parallel repetition.

I will begin with an introductory survey of direct products and parallel repetition in the classical setting, and then move to talk about extensions to the quantum setting. Namely, where the game is classical but the provers share an entangled quantum state.

I will describe a recent result (joint with David Steurer and Thomas Vidick) that gives an upper bound to the entangled value of the n-fold repeated game that decreases exponentially with n. This result holds for a broad class of games called "projection games."

The proof extends a recent "analytical / linear algebraic" proof for classical parallel repetition of projection games. An interesting new ingredient is a quantum analog to Holenstein's correlated sampling lemma, generalizing recent results on universal embezzlement to an approximate scenario: Two isolated parties, given classical descriptions of bipartite states x,y respectively such that x \approx y , are able to locally generate a joint entangled state z \approx x \approx y using an initial entangled state that is independent of their inputs.