We prove that for all $\varepsilon>0$, there exists a positive integer $k$ such that given a $4$-to-$1$ Game $\Psi$ with alphabet size at most $k$, it is NP-hard to distinguish between the case that val$(\Psi)=1$ and the case that val$(\Psi)\leq \delta$. This confirms the $4$-to-$1$ Games Conjecture from [Khot, CCC ... more >>>

Set-disjointness is one of the most fundamental and widely studied problems in the area of communication complexity. In this problem, each party $i$ receives a set $S_i\subseteq [N]$. The goal is to determine whether $\bigcap S_i$ is empty via communication between players. The decision version simply asks if the common ... more >>>