AF: Small: New Directions in Computational Geometry

该奖项旨在寻求计算几何新领域的进展：特别是集体行为、次线性、遗传结构和低熵几何算法。最近在多智能体协议系统上的工作揭示了几何方法对该主题的巨大潜力。一个新的生成函数，“总s能量”，对共识的研究显示出相当大的希望。对这种新装置进行彻底的研究是这个项目的出发点。几何数据倾向于捕获大量的相干性，因此熵很小。这个项目的第二部分着眼于这种现象的四个实例：马尔可夫源、遗传复杂性、次线性计算和自改进几何算法。在第一种情况下，数据由马尔可夫链生成；在第二种情况下，它是在一个明确给出的更大的结构中呈现的；在第三种情况下，通过随机抽样只能获得有限数量的数据；在第四种情况下，它来自未知的无记忆低熵分布。在所有情况下，目标都是一样的：超越最坏情况分析，为更现实的分析框架腾出空间。

This award seeks progress in new areas of computational geometry: specifically, collective behavior, sublinearity, hereditary structures, and low-entropy geometric algorithms. Recent work on multiagent agreement systems has revealed the great potential of a geometric approach to the subject. A new generating function, the "total s-energy", shows considerable promise for the study of consensus. A thorough investigation of this new device is the starting point of this project. Geometric data tends to capture a vast amount of coherence and hence little entropy. The second part of this project looks at four instances of this phenomenon: Markov sources, hereditary complexity, sublinear computing, and self-improving geometric algorithms. In the first case, the data is generated by a Markov chain; in the second, it is presented within a larger structure that is given explicitly; in the third, the data is only accessible in limited amounts through random sampling; in the fourth, it comes from an unknown memoryless low-entropy distribution. In all cases, the objective is the same: to go beyond worst-case analysis and make room for a more realistic analytical framework.