Discrete Geometry and Communication Complexity

假设你有一个正方形网格(矩阵)，每个位置都有一个符号或-。这样的矩阵可用于对数学和计算机科学中的各种问题进行建模。了解这些迹象的模式有多么复杂，这一点往往很重要。有两种自然的方法来评估模式的复杂性。(1)模式看起来有多复杂？是否存在模式非常简单的大区域：例如，所有区域？(2)以代数方式(通过使用简单的数学运算)生成模式有多难？例如，你能在低维空间中找到点，让这些点之间的角度告诉你矩阵中的符号吗？第一个复杂性衡量标准很容易检测，通常也很容易预测(例如，如果符号是由随机过程产生的)。复杂性的第二个衡量标准是最有可能影响网格在实际问题中的行为的标准。我们希望能够将这两种复杂性衡量标准联系起来。要做到这一点令人惊讶地困难。这个项目的目的是利用离散几何学(高维空间中点集的几何学)的洞察力来理解这两种类型的复杂性的相关程度。长期目标将是验证或有助于验证对数等级猜想，该猜想以定量的方式陈述，如果矩阵可以从低维空间(远低于矩阵的大小)中的点以代数方式生成，则矩阵必须具有大的常号矩形区域(至少在重新排序行和列之后)。在其他方面，这样的结构原理将澄清和设置重要的过去的研究表明，随机符号矩阵不能从低维空间生成的背景。

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.