ECCC-Report TR14-135https://eccc.weizmann.ac.il/report/2014/135Comments and Revisions published for TR14-135en-usFri, 08 Jul 2016 14:27:35 +0300
Revision 2
| Sign rank, VC dimension and spectral gaps |
Shay Moran,
Amir Yehudayoff,
Noga Alon
https://eccc.weizmann.ac.il/report/2014/135#revision2This work studies the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is {three}. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. For $d >2$, similar but slightly less accurate statements hold. {The lower bounds improve over previous ones by Ben-David et al., and the upper bounds are novel.}
The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve.
The upper bound technique is also used to: (i) provide estimates on the number of classes of a given VC dimension, and the number of maximum
classes of a given VC dimension -- answering a question of Frankl from '89,
and (ii) design an efficient algorithm that provides an $O(N/\log(N))$ multiplicative approximation for the sign rank.
We also observe a general connection between sign rank and spectral gaps which is based on Forster's argument. Consider the $N \times N$ adjacency matrix of a $\Delta$ regular graph with a second eigenvalue of absolute value $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. We use this connection to prove the existence of a maximum class $C\subseteq\{\pm 1\}^N$ with VC dimension $2$ and sign rank $\tilde{\Theta}(N^{1/2})$. This answers a question of Ben-David et al.~regarding the sign rank of large VC classes. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.
We further describe connections to communication complexity, geometry,
learning theory, and combinatorics.
Fri, 08 Jul 2016 14:27:35 +0300https://eccc.weizmann.ac.il/report/2014/135#revision2
Revision 1
| Sign rank versus VC dimension |
Shay Moran,
Amir Yehudayoff,
Noga Alon
https://eccc.weizmann.ac.il/report/2014/135#revision1We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. For $d >2$, similar but slightly less accurate statements hold.
The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve. The upper bound technique also yields an efficient
algorithm that provides an $O(N/\log(N))$ multiplicative approximation for the sign rank (Bhangale and Kopparty proved that deciding if the sign rank is at most $3$ is NP-hard).
We also observe a general connection between sign rank and spectral gaps which is based on Forster's argument. Consider the $N \times N$ adjacency matrix of a $\Delta$ regular graph with a second eigenvalue of absolute value $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.
We further describe connections to communication complexity, geometry, learning theory, and combinatorics.Thu, 26 Mar 2015 09:42:21 +0200https://eccc.weizmann.ac.il/report/2014/135#revision1
Paper TR14-135
| Sign rank, VC dimension and spectral gaps |
Shay Moran,
Amir Yehudayoff,
Noga Alon
https://eccc.weizmann.ac.il/report/2014/135We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe connections to combinatorics, communication complexity and learning theory.
We also provide explicit examples of matrices with low VC dimension and high sign rank. Let $A$ be the $N \times N$ point-hyperplane incidence matrix of a finite projective geometry with order $n \geq 3$ and dimension $d \geq 2$. The VC dimension of $A$ is $d$, and we prove that its sign rank is larger than $N^{\frac{1}{2}-\frac{1}{2d}}$. The large sign rank of $A$ demonstrates yet another difference between finite and real geometries.
To analyse the sign rank of $A$, we introduce a connection between sign rank and spectral gaps, which may be of independent interest. Consider the $N \times N$ adjacency matrix of a $\Delta$ regular graph with a second eigenvalue in absolute value $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. A similar statement holds for all regular (not necessarily symmetric) sign matrices. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.Fri, 24 Oct 2014 11:03:39 +0300https://eccc.weizmann.ac.il/report/2014/135