BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/127
DTSTAMP:20230914T125911Z
SUMMARY:The Parallel Repetition Theorem and Related Results
DESCRIPTION:Speaker: Rakesh Venkat\nSchool of Technology and Computer Scien
 ce\nTata Institute of Fundamental Research\nHomi Bhabha Road\n\nAbstract: 
 \nIn a 2-Prover 1-Round Game\, a verifier draws a pair of questions (X\,Y 
 ) from a distribution D  and sends one each to two co-operating\, non-comm
 unicating players who need to respond back with answers A\,B. The verifier
  checks the answers using a known predicate V(X\,Y\,A\,B)\, and declares a
  win or loss. The aim of the players is to plan a strategy to win the game
  with the highest probability over the set of questions. The n -fold paral
 lel repetition of the game has the verifier drawing n  pairs of \, i.i.d.\
 , and sending each player an n-tuple of questions. The players have to res
 pond with n answers each\, one for each co-ordinate. The Parallel Repetiti
 on theorem proven by Raz states that the probability of winning the repeat
 ed game in all co-ordinates drops exponentially with n. The theorem was a 
 key result used in proving various hardness of approximation results. In t
 his talk\, we give a brief overview of the implications of this theorem\, 
 and various related results.\n
URL:https://www.tcs.tifr.res.in/web/events/127
DTSTART;VALUE=DATE:20101124
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR