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, ... more >>>

Recently, Göös et al. (2024) showed that Res ? uSA = RevRes in the following sense: if a formula $\varphi$ has refutations of size at most $s$ and width/degree at most $w$ in both Res and uSA, then there is a refutation for $\varphi$ of size at most $poly(s·2^w)$ in ... more >>>

We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where $a$ bits are communicated per round, then the \emph{batch language} $\mathcal{L}^{\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $\mathcal{L}$, has an unambiguous interactive proof with round complexity ... more >>>