Seminars & Colloquia Calendar

Download as iCal file

Graduate Student Combinatorics Seminar Sponsored by DIMACS

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.