Campus Event Calendar
Event Entry
What and Who
Sign rank, VC dimension and spectral gaps
Shay Moran
Max-Planck-Institut für Informatik - D1
AG1 Advanced Mini-Course
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 12 December 2014
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
The sign-rank 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 sign-rank Omega(N^{1/4}). I will also discuss the maximum possible sign-rank of an N by N matrix with VC-dimension d. Finally, I will mention the applications of these results to communication complexity and learning theory.
Joint work with Noga Alon and Amir Yehudayoff
Contact
Shay Moran
--email hidden
passcode not visible
logged in users only
Shay Moran, 11/27/2014 23:19
Shay Moran, 11/27/2014 23:18 -- Created document.
Shay Moran, 11/27/2014 23:18 -- Created document.