Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-161 | 28th October 2025 20:43

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics

RSS-Feed




TR25-161
Authors: Kunal Mittal
Publication: 28th October 2025 21:37
Downloads: 141
Keywords: 


Abstract:

We show equivalences between several high-dimensional problems in extremal combinatorics and parallel repetition of multiplayer (multiprover) games over large answer alphabets. This extends the forbidden-subgraph technique, previously studied by Verbitsky (Theoretical Computer Science 1996), Feige and Verbitsy (Combinatorica 2002), and H{\k a}z{\l}a, Holenstein and Rao (2016), to all $k$-player games, and establishes new connections to problems in combinatorics. We believe that these connections may help future progress in both fields.



ISSN 1433-8092 | Imprint