BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/757
DTSTAMP:20230914T125937Z
SUMMARY:Multiplayer Parallel Repetition for Expanding Games
DESCRIPTION:Speaker: Rakesh Venkat (School of Technology and Computer Scien
 ce\nTata Institute of Fundamental Research\nHomi Bhabha Road\nNavy Nagar\n
 Mumbai 400005)\n\nAbstract: \nA two-player game is an important construct 
 used in proving many hardness of approximation results. It consists of two
  non-communicating players\, Alice and Bob\, trying to win against a verif
 ier $V$\, who draws a question pair $(x\,y) \\in X  \\times Y$ from a kno
 wn distribution $D$ and sends $x$ to Alice and $y$ to Bob. The goal of Ali
 ce and Bob is to come up with strategies to provide answers ($a(x)\, b(y)$
  resp.) to these questions\, in order to win (decided by a predicate V(x\,
 y\,a\,b)) with maximum probability over $D$.  This maximum probability  
 is called the value of the game.\n\nRaz first showed that repeating a two-
 player game in parallel $n$-times (where $n$ question pairs are drawn inde
 pendently and given to the players simultaneously) drives down the probabi
 lity of the players winning all the rounds exponentially with $n$. A serie
 s of subsequent works improved the parameters involved\, and current known
  results are near-optimal.\n\nIn contrast to two-player games\, very littl
 e is known about the parallel-repetition of games with $k$ players for $k\
 \geq 3$.  The only known universal upper bound  on the value of a $n$-re
 peated\, $k$-player game is due to Verbitsky\;  it shows a weak inverse-A
 ckermann decay with regards to $n$.  Some special classes of multi-player
  games (free games and anchored games) have been shown to exhibit  expone
 ntial decay in value. The technical roadblock  in extending known proofs 
 for $k=2$  to $k \\geq 3$ is similar to one encountered in proving direct
  product results in communication complexity with 3 or more players.\n\nIn
  this work\, we show that under $n$-fold repetition\, a large class of $k$
 -player games do\, in fact\, exhibit an exponential decay in value. These 
 games are expanding in a specific sense. Our result recovers exponential d
 ecay theorems for free and anchored games as a corollary. We also point ou
 t a simple game not handled by the above class\, and conjecture that it is
  in fact\, the hardest case (oint work with Irit Dinur\, Prahladh Harsha a
 nd Henry Yuen).\n \n
URL:https://www.tcs.tifr.res.in/web/events/757
DTSTART;TZID=Asia/Kolkata:20170224T160000
DTEND;TZID=Asia/Kolkata:20170224T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR