Kunal Mittal will present his FPO "Parallel Repetition of Multiplayer Games: New Bounds and Applications" on August 1, 2025 at 12pm is CS 302 and Zoom. The committee is as follows: Examiners: Ran Raz (adviser), Gillat Kol,Mark Braverman Readers: Pravesh Kothari and Zeev Dvir Zoom Link: [ https://princeton.zoom.us/j/98962124632?pwd=9Or6rUipHulgmrqsgRfqvIn24haJzh.1 | https://princeton.zoom.us/j/98962124632?pwd=9Or6rUipHulgmrqsgRfqvIn24haJzh.1 ] Meeting ID: 989 6212 4632 Passcode: 750823 All are welcome to attend. Abstract: This thesis studies the parallel repetition of multiplayer games. These games were first (implicitly) introduced in quantum mechanics, to study quantum entanglement with regard to local hidden-variable theories, in the context of the Einstein-Podolsky-Rosen (EPR) paradox. Later, multiplayer games were formally defined and extensively studied in complexity theory, in the framework of interactive proof systems and probabilistically checkable proofs (PCPs). Parallel repetition is a natural hardness-amplification technique used to decrease the value of multiplayer games while maintaining their single-round structure. Despite its apparent simplicity, analyzing the effects of parallel repetition on the value of a game remains a challenging problem, particularly for games involving three or more players. This work makes two main contributions: establishing stronger bounds on the value of parallel repetition for several classes of multiplayer games, and developing new connections to computational complexity and extremal combinatorics. In our first contribution, we substantially improve the best-known bounds on the value of parallel repetition for several classes of multiplayer games. In particular, we prove an inverse-polynomial bound for all 3-player games with 1-bit questions, as well as an inverse polynomial bound for a very large class of k-player games called playerwise-connected games. Furthermore, we prove exponential bounds for certain special 3-player games like the anticorrelation game. Prior to our work, nothing better than weak inverse-Ackermann bounds were known, for any of these games. Our second contribution shows that a sufficiently strong parallel repetition theorem for a special case of multiplayer games implies super-linear lower bounds for multi-tape Turing machines with advice, which is a long-standing open problem in complexity theory. Additionally, we demonstrate equivalences between several high-dimensional problems in extremal combinatorics and parallel repetition of multiplayer games over large answer alphabets.