# 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.

Charles Weibel Organizer's Page

Brooke Logan

Wujun Zhang Organizer's webpage

P. Gupta, X.Huang and J. Song Organizer's webpage

Swastik Kopparty, Sepehr Assadi Seminar webpage

Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage

Yonah Biers-Ariel, Mingjia Yang, and Doron Zeilberger --> homepage

Paul Feehan, Manousos Maridakis, Natasa Sesum Organizer's webpage

Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage

Jason Saied Seminar webpage

Brian Pinsky, Rashmika Goswami website

Corrine Yap Organizer's webpage

James Holland; Organizer website

Edna Jones Organizer's webpage

Brooke Ogrodnik website

Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum

Organizer: Luochen Zhao

Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song

Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage

Simon Thomas website

Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page

Joel Lebowitz, Michael Kiessling

Yanyan Li, Haim Brezis

Stephen D. Miller, John C. Miller, Alex V. Kontorovich, Alex Walker seminar website

Stephen D. Miller

Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum

Yael Davidov Seminar webpage

Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page

Ebru Toprak, Organizer

Fioralba Cakoni Seminar webpage

- Show events from all categories

## 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.*