| The sign-rank of an N by 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 by N matrices with VC-dimension 2 and sign-rank Omega(N^{1/4}). I will also discuss the maximum possible sign-rank of an N by N matrix with VC-dimension d. Finally, I will mention the applications of these results to communication complexity and learning theory.
Joint work with Noga Alon and Amir Yehudayoff |
