Lower Bounds for Approximate Sign Rank
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913160977448960 |
|---|---|
| author | Bindua, Riju Hatami, Hamed Karimi, Hasti Robere, Robert |
| author_facet | Bindua, Riju Hatami, Hamed Karimi, Hasti Robere, Robert |
| contents | We prove new upper and lower bounds on $ε$-approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \times n$ sign matrix with approximate sign-rank $d$ contains a monochromatic rectangle of size $d^{-O(d)}m \times d^{-O(d^2)}n$, paralleling classical results for exact sign-rank. As an application, we establish a lower bound of $Ω(\sqrt{d/\log d})$ on the $ε$-approximate sign-rank of large-margin $d$-dimensional half-spaces. Prior to our work, the only general lower bound technique known for approximate sign-rank yielded bounds of strength $ε^{-1} - 1$, which are constant for fixed $ε$.
A key ingredient is a new geometric theorem on hyperplane avoidance: for any set of $n$ points in general position in $\mathbb{R}^d$, there exist $d$ subsets, each of size $d^{-O(d)} n$, such that no hyperplane simultaneously splits all of them. The proof combines the Forster-Barthe isotropic position theorem with the Bourgain-Tzafriri restricted invertibility principle.
We also study the relationship between approximate sign-rank and VC dimension. We prove a lower bound on approximate sign-rank in terms of VC dimension, and exhibit concept classes of VC dimension $2$ with large approximate sign-rank.
Finally, we study the approximate sign-rank of the $2^m \times 2^m$ Hadamard matrix $H_m$. The sign-rank of $H_m$ is known to be $Ω(\sqrt{2^m})$ by Forster's classic theorem. Contrasting this, we adapt an argument of Alman and Williams to show that the approximate sign-rank of $H_m$ is at most $m^{O(\sqrt{m} \log(1/ε))}$, and hence the Hadamard matrix does not witness polynomial-strength lower bounds for approximate sign-rank. Using our VC dimension bound, we prove that the approximate sign-rank of $H_m$ is at least $Ω_ε(m)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_01038 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Approximate Sign Rank Bindua, Riju Hatami, Hamed Karimi, Hasti Robere, Robert Computational Complexity We prove new upper and lower bounds on $ε$-approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \times n$ sign matrix with approximate sign-rank $d$ contains a monochromatic rectangle of size $d^{-O(d)}m \times d^{-O(d^2)}n$, paralleling classical results for exact sign-rank. As an application, we establish a lower bound of $Ω(\sqrt{d/\log d})$ on the $ε$-approximate sign-rank of large-margin $d$-dimensional half-spaces. Prior to our work, the only general lower bound technique known for approximate sign-rank yielded bounds of strength $ε^{-1} - 1$, which are constant for fixed $ε$. A key ingredient is a new geometric theorem on hyperplane avoidance: for any set of $n$ points in general position in $\mathbb{R}^d$, there exist $d$ subsets, each of size $d^{-O(d)} n$, such that no hyperplane simultaneously splits all of them. The proof combines the Forster-Barthe isotropic position theorem with the Bourgain-Tzafriri restricted invertibility principle. We also study the relationship between approximate sign-rank and VC dimension. We prove a lower bound on approximate sign-rank in terms of VC dimension, and exhibit concept classes of VC dimension $2$ with large approximate sign-rank. Finally, we study the approximate sign-rank of the $2^m \times 2^m$ Hadamard matrix $H_m$. The sign-rank of $H_m$ is known to be $Ω(\sqrt{2^m})$ by Forster's classic theorem. Contrasting this, we adapt an argument of Alman and Williams to show that the approximate sign-rank of $H_m$ is at most $m^{O(\sqrt{m} \log(1/ε))}$, and hence the Hadamard matrix does not witness polynomial-strength lower bounds for approximate sign-rank. Using our VC dimension bound, we prove that the approximate sign-rank of $H_m$ is at least $Ω_ε(m)$. |
| title | Lower Bounds for Approximate Sign Rank |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2605.01038 |