Sign-Rank of $k$-Hamming Distance is Constant
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909787793391616 |
|---|---|
| author | Göös, Mika Harms, Nathaniel Imbach, Valentin Sokolov, Dmitry |
| author_facet | Göös, Mika Harms, Nathaniel Imbach, Valentin Sokolov, Dmitry |
| contents | We prove that the sign-rank of the $k$-Hamming Distance matrix on $n$ bits is $2^{O(k)}$, independent of the number of bits $n$. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (RANDOM 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the sign-rank should depend on $n$. This conjecture would have qualitatively separated margin from sign-rank (or, equivalently, bounded-error from unbounded-error randomized communication). In fact, our technique gives constant sign-rank upper bounds for all matrices which reduce to $k$-Hamming Distance, as well as large-margin matrices recently shown to be irreducible to $k$-Hamming Distance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12022 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sign-Rank of $k$-Hamming Distance is Constant Göös, Mika Harms, Nathaniel Imbach, Valentin Sokolov, Dmitry Computational Complexity 68Q15 F.1.3 We prove that the sign-rank of the $k$-Hamming Distance matrix on $n$ bits is $2^{O(k)}$, independent of the number of bits $n$. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (RANDOM 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the sign-rank should depend on $n$. This conjecture would have qualitatively separated margin from sign-rank (or, equivalently, bounded-error from unbounded-error randomized communication). In fact, our technique gives constant sign-rank upper bounds for all matrices which reduce to $k$-Hamming Distance, as well as large-margin matrices recently shown to be irreducible to $k$-Hamming Distance. |
| title | Sign-Rank of $k$-Hamming Distance is Constant |
| topic | Computational Complexity 68Q15 F.1.3 |
| url | https://arxiv.org/abs/2506.12022 |