The cover number of a matrix and its applications

Noga Alon, Tel Aviv University and IAS, Princeton
Sep 30 2013 - 4:30pm
Event type: 
PACM Colloquium
Fine 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.