Title: Sign Rank, Spectral Gap and VC dimension
Speaker: Noga Alon, IAS/Tel Aviv University
Date: Wednesday, December 3, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The signrank 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 signrank Omega(N^{1/4}). I will also discuss the maximum possible signrank of an N by 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.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/