# Seminars & Colloquia Calendar

## Parallel repetition of games

#### Aditya Potukuchi

Location: ** Hill 701, GSL**

Date & time: Wednesday, 05 February 2020 at 12:15PM - 1:15PM

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.