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