Computer Science/Discrete Mathematics Seminar II

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.