Skip to content Skip to navigation
Seminar
12/3/2014 11:00 am
CoRE A(Room 301)

Sign Rank, Spectral Gap and VC dimension

Noga Alon, IAS/Tel Aviv University

Organizer(s): Swastik Kopparty and Shubhangi Saraf

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.