AF: Small: Understanding Expansion Phenomena: Graphical, Hypergraphical, Geometric, and Quantum

计算中的各种现象可以看作是不同形式的“展开”，它确保了可以通过观察对象的小部分来观察的局部性质，可以用来影响和理解在更大范围内表现出的全局性质。这是几个应用中的重要设计要求，例如(1)经典和量子纠错，其中人们希望通过局部检查容易地检测到错误，(2)优化问题，其中人们希望局部选择将全局解推向最优，以及(3)高维数据的几何嵌入，其中人们希望使用局部(低维)条件来影响高维行为。在过去的几年里，出现了一些新的概念和技术来研究不同背景下的扩张现象。这个项目的目的是以统一的方式研究几种不同形式的扩展现象，重点是在纠错码和(近似)优化领域的应用。这项研究可能会在这些现象有用的多个领域之间产生新的联系。作为这项研究的一部分而产生的材料还将通过调查和一系列说明性视频进行传播。本项目旨在获得以下不同形式和应用的扩展现象的统一观点：-超图的图扩展的经典概念和高维扩展的新概念，以及它们与编码理论的最新进展的联系。-经典扩展现象在量子编码中的应用，以及经典扩展现象的量子扩展。-高维扩展与几何空间中扩展现象的研究和可逼近性的联系，以及有关细粒度图扩展的相关问题。本项目所追求的研究方向是在算法编码理论以及离散和连续优化问题的可逼近研究中引入新的技术。该项目考虑了几个已被证明是当前算法和分析技术的瓶颈的问题，探索了在不同背景下研究扩展所产生的新方法。该项目旨在将这些想法应用于设计新的纠错码，以及现有码的新算法，用于设计新的伪随机对象，以及用于证明不可逼近结果的新的组合和几何实例家族。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

A broad variety of phenomena in computation can be viewed as different forms of “expansion”, which ensure that local properties which can be observed by looking at small parts of an object, can be used to influence and understand global properties exhibited at a much larger scale. This is an important design requirement in several applications, such as (1) classical and quantum error-correction, where one wants errors to be easily detectable by local checks, (2) optimization problems, where one wants local choices to push the global solution towards optimality, and (3) geometric embeddings of high-dimensional data, where one wants to use local (low-dimensional) conditions to influence high-dimensional behavior. In the past few years, several new concepts and techniques have emerged to study expansion phenomena in different contexts. This project aims to study several different forms of expansion phenomena in a unified way, with an emphasis on applications in the areas of error-correcting codes and (approximate) optimization. This research is likely to lead to new connections between multiple areas where such phenomena are useful. The material generated as part of this research will also be disseminated through surveys and a series of expository videos. This project aims to obtain a unified view of the following different forms and applications of expansion phenomena:- Classical notions of graph expansion and novel notions of high-dimensional expansion for hypergraphs, and their connections to recent advances in coding theory.- Applications of classical expansion phenomena to quantum codes, as well as quantum extensions of classical expansion phenomena.- Connections of high-dimensional expansion to the study and approximability of expansion phenomena in geometric spaces, and related problems about fine-grained graph expansion.The research directions pursued in this project aim to introduce new techniques in algorithmic coding theory and in the study of approximability of discrete and continuous optimization problems. The project considers several problems that have proved to be bottlenecks for current algorithmic and analytic techniques, explores new approaches arising from the study of expansion in a different context. The project aims to apply these ideas for the design of new error-correcting codes, and new algorithms for existing codes, towards the design of new pseudorandom objects, and also new families of combinatorial and geometric instances for proving inapproximability results.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.