BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/532
DTSTAMP:20230914T125928Z
SUMMARY:Small Value Parallel Repetition for General Games
DESCRIPTION:Speaker: Ankit Garg (Princeton University\nDepartment of Comput
er Science\n35\, Olden Street\nPrinceton\, NJ 08544\nUnited States of Amer
ica)\n\nAbstract: \nAbstract: We prove a parallel repetition theorem for g
eneral games with value tending to 0. Previously Dinur and Steurer proved
such a theorem for the special case of projection games. We use informatio
n theoretic techniques in our proof. Our proofs also extend to the high va
lue regime (value close to 1) and provide alternate proofs for the paralle
l repetition theorems of Holenstein and Rao for general and projection gam
es respectively. We also extend the example of Feige and Verbitsky to show
that the small-value parallel repetition bound we obtain is tight. Our te
chniques are elementary in that we only need to employ basic information t
heory and discrete probability in the small-value parallel repetition proo
f (this is joint work with Mark Braverman).\n
URL:https://www.tcs.tifr.res.in/web/events/532
DTSTART;TZID=Asia/Kolkata:20140821T160000
DTEND;TZID=Asia/Kolkata:20140821T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR