![Real Analysis in Computer Science_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Real%20Analysis%20in%20Computer%20Science_hi-res.jpg?h=e2b42a27&itok=jpgiJZrK)
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.