Seminars & Colloquia Calendar

Date: February 5, 2020
Speaker: Aditya Potukuchi
Time: 12:15PM
Place: Graduate Student Lounge, 7th Floor, Hill Center
Title: Parallel repetition of games
Abstract: Consider a "game" involving two players Alice and Bob (as a team), who coordinate on a strategy beforehand. The following describes one round of the "game":
1. You sample a couple of (not necessarily independent) random variables x and y, and give Alice x, and Bob y. For example, think of x and y as two parts of a question in a quiz show.
2. Alice returns with answer a, and Bob returns with an answer b without communicating.
3. They (Alice+Bob) win if V(x,y,a,b) = 1 for some function V chosen beforehand. For example, if a+b is the answer to the question x+y in the quiz show.
Let p be the maximum probability (over all strategies) that Alice+Bob win the round. Here is the question: Suppose you independently sampled a bunch of tuples (x1,y1),(x2,y2),....,(xt,yt), gave Alice all the xi's and Bob all the yi's, what is the maximum probability that they win _all_ the rounds? It's obviously pt right? Since they can't communicate and the questions are chosen independently..... This is (strangely) not quite the case. In fact, showing that it even goes down exponentially with t itself is quite difficult and is commonly called the "Parallel Repetition Theorem". I will talk about this theorem and some ideas behind the proof.