We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

more >>>

We study boolean constraint satisfaction problems (CSPs) $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ for all predicates $f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer $v$ and a list of constraints over $n$ boolean variables, each obtained by applying $f$ to a sequence of literals, we wish ... more >>>

In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate $\gamma_2$-factorization norm is a lower bound for these parameters and asked whether a stronger ... more >>>