We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of the Gap Hamming Distance problem is $O(1)$ while its unbounded-error communication complexity is $\Omega(\log(n))$.

Previously, it was unknown whether the unbounded-error communication complexity could be asymptotically larger than the randomized communication complexity.

In connection to learning theory, we prove that, despite its learnability properties, the class of large margin half-spaces in $\mathbb{R}^d$ is genuinely high-dimensional, i.e., it cannot be embedded in $\mathbb{R}^{d-1}$. This result is closely related to a recent conjecture of Alon, Hanneke, Holzman, and Moran (FOCS 2021) about the VC dimension of this class.

Our final application is to the theory of dimension reductions. The Johnson-Lindenstrauss theorem implies that any set of $N$ unit vectors is embeddable in dimension $O(\gamma^{-2}\log N)$ without altering the signs of those pairwise inner products that have absolute values at least $\gamma>0$. Our result establishes the tightness of this bound, which answers a question of Linial, Mendelson, Schechtman, and Shraibman (Combinatorica, 27(2007)) in the case of partial functions.