A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications

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 unboundederror 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 Ω(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 R d is genuinely high-dimensional, i.e., it cannot be embedded in 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(γ -2 log N ) without altering the signs of those pairwise inner products that have absolute values at least γ > 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.