Sign rank, spectral gap and VC dimension

The signrank of an $N \times N$ matrix $A$ of signs is the minimum possible rank of a real matrix $B$ in which every entry has the same sign as the corresponding entry of $A$. The VC-dimension of $A$ is the maximum cardinality of a set of columns $I$ of $A$ so that for every subset $J$ of $I$ there is a row $i$ of $A$ so that $A_{ij}=+1$ for all $j$ in $J$ and $A_{ij}=-1$ for all $j$ in $I-J$. I will describe explicit examples of $N \times N$ matrices with VC-dimension 2 and signrank $\Omega(N^{1/4})$. I will also discuss the maximum possible signrank of an $N \times N$ matrix with VC-dimension $d$. We conjecture that this maximum is $N^{1-1/d}$, up to logarithmic factors, and can prove that this is the case for $d \leq 2$. I will also mention briefly the applications of these results to communication complexity and learning. Joint work with Shay Moran and Amir Yehudayoff.