Abstract

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.

Video Recording