The cover number of a matrix and its applications

Monday, September 30, 2013 -
4:30pm to 5:30pm
The (epsilon)-cover number of a matrix A with entries in [-1,1] is the minimum number of aligned cubes of edge-length epsilon that are needed to cover the convex hull of the columns of A. The study of this notion is motivated by algorithmic applications and leads to intriguing combinatorial, extremal and probabilistic questions regarding the connection of this notion and other complexity measures of the matrix including its rank, approximate rank, VC dimension and more.  Most of the recent results are based on joint work with Lee, Shraibman and Vempala.
Speaker: 
Noga Alon
Tel Aviv University and IAS, Princeton
Event Location: 
Fine Hall 214