Multiplayer Parallel Repetition for Three-Player Games on Binary Inputs

Explore the intricacies of multiplayer parallel repetition in three-player games with binary inputs in this 48-minute lecture by Uma Girish at the Centre de recherches mathématiques (CRM). Delve into the central problem of parallel repetition in complexity theory and its applications to PCPs, hardness of approximation, quantum information, and communication complexity. Examine the challenges of multiplayer games, where players receive questions from a joint distribution and must provide answers satisfying a predicate. Investigate the exponential decay in winning probability for two-player games and the open conjecture for games with three or more players. Learn about the latest advancements in three-player games with binary inputs, including polynomial decay in winning probability. Survey the landscape of multiplayer parallel repetition, explore state-of-the-art results, and gain insights into connected games, GHC games, and anticorrelation games. Discover the concept of bowtie distributions and delve into combinatorial problems and Fourier analytic techniques used in this field.

Introduction
Multiplayer parallel repetition
Multiplayer games
Quantum mechanics
What is parallel repetition
Parallel Interpretation
Connected games
Main result
Connected game
GHC game
Anticorrelation game
What is a bowtie
bowtie distribution
mainlemma
combinatorial problems
Fourier analytic techniques
Linear functions