Discrete Geometry and Communication Complexity

假设给你一个正方形网格（矩阵），每个位置都有一个符号，+或-。这样的矩阵可以用来模拟数学和计算机科学中的各种问题。了解这些标志的模式有多复杂通常是很重要的。有两种自然的方法来评估模式的复杂性。这个图案看起来有多复杂？是否存在模式非常简单的大区域：例如all + ？(2)用代数方法（通过简单的数学运算）生成模式有多困难？例如，你能否在低维空间中找到点，让这些点之间的夹角告诉你矩阵中的符号？复杂度的第一种度量很容易检测，通常也很容易预测（例如，如果符号是由随机过程产生的）。复杂性的第二种度量是在实际问题中最有可能影响网格行为的一种。我们希望能够把这两种复杂性的度量联系起来。做到这一点出奇地困难。这个项目的目的是利用离散几何（高维空间中点集的几何）的见解来理解这两种复杂性的关联程度。长期目标将是验证，或有助于验证log-rank猜想，该猜想以定量的方式表明，如果矩阵可以从低维空间（远低于矩阵的大小）中的点代数生成，那么矩阵必须具有大的常符号矩形面积（至少在重新排序行和列之后）。除其他事项外，这样的结构原则将澄清和背景重要的过去的研究表明，随机符号矩阵不能从低维空间产生。

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.