ECCC-Report TR22-130https://eccc.weizmann.ac.il/report/2022/130Comments and Revisions published for TR22-130en-usFri, 16 Sep 2022 05:54:31 +0300
Paper TR22-130
| A Borsuk-Ulam lower bound for sign-rank and its application |
Hamed Hatami,
Kaave Hosseini,
Xiang Meng
https://eccc.weizmann.ac.il/report/2022/130 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.
Fri, 16 Sep 2022 05:54:31 +0300https://eccc.weizmann.ac.il/report/2022/130