Discrete Geometry and Communication Complexity

Suppose you are given a square grid (matrix) with each position occupied by a sign, + or -. Such a matrix can be used to model a variety of problems in mathematics and computer science. It is often important to understand how complex is the pattern of the signs. There are two natural ways to assess the complexity of the pattern.(1) How complex does the pattern look? Are there large areas in which the pattern is very simple: all + for example?(2) How difficult is it to generate the pattern algebraically (by using simple mathematical operations)? For example, can you find points in a low-dimensional space, so that the angles between these points tell you the signs in the matrix?The first measure of complexity is easy to detect and usually easy to predict (for example, if the signs are generated by a random process). The second measure of complexity is the one most likely to affect the behaviour of the grid in practical problems. We would like to be able to relate these two measures of complexity. It is surprisingly difficult to do so. The aim of this project is to use insights from discrete geometry (the geometry of sets of points in high-dimensional space) to understand the extent to which the two types of complexity are related. The long term goal will be to verify, or contribute to a verification, of the log-rank conjecture which states in a quantitative way that if the matrix can be generated algebraically from points in a low-dimensional space (much lower than the size of the matrix) then the matrix must have large rectangular areas of constant sign (at least after reordering of the rows and columns). Among other things, such a structural principle would clarify and set in context important past research showing that random sign-matrices cannot be generated from spaces of low dimension.