Sign rank, spectral gap and VC dimension

Computer Science/Discrete Mathematics Seminar II
Topic:Sign rank, spectral gap and VC dimension
Speaker:Noga Alon
Affiliation:Tel Aviv University; Visiting Professor, School of Mathematics
Date:Tuesday, November 4
Time/Room:10:30am - 12:30pm/S-101
Video Link:http://video.ias.edu/csdm/2014/1104-NogaAlon

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.