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.