The cover number of a matrix and its applications

The cover number of a matrix and its applications

-
Noga Alon, Tel Aviv University and IAS, Princeton
Fine Hall 214

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.