Fall 2013

The Structure of Low Rank Matrices

Thursday, Dec. 5, 2013 9:30 am10:15 am PST

Add to Calendar

The structure of low rank matrices plays an important role in several fields of theoretical computer science, such as communication complexity, arithmetic circuits lower bounds and constructions of pseudo-random graphs. In particular, the following Ramsey-type question is of interest: given a matrix which is both low rank and sparse, what is the size of the largest zero rectangle that it must have? I will describe the connections of this problem to the above mentioned fields, some recent advances on it, and its relations to additive combinatorics.