CAREER: Higher-Order Interactions in Tensors and Isomorphism Problems

大数据在当今世界变得越来越重要-它不仅有可能解决社会中的关键问题，而且还可能加剧或制造新的问题。正因为如此，正确理解大型数据集是一项至关重要的努力。今天的大数据集通常由大量成对交互来建模，即两个实体之间的交互，如人、公司或分子。然而，这种成对互动可能会错过重要的现象，如多家公司达成贸易协议，一种化学物质催化其他几种化学物质的反应，或一项使用多种技术的单一专利。幸运的是，使用张量的数学可以准确地模拟大数据集中的这些“更高层次”的相互作用。张量正在迅速成为21世纪的基本数据结构和关键的数学对象，就像过去200年来线性代数主导科学和工程一样。张量是广泛领域的核心，从基础物理到机械工程，从量子计算到神经网络和深度学习。在计算机科学中，它们出现在密码学、用于矩阵相乘等关键任务的算法，以及跨越计算机科学和数学的最深层次的问题(暴力搜索算法是否总是可以改进，臭名昭著的P与NP问题)。这个项目的目标是更深入地了解张量的计算性质，并发展超成对相互作用的数学和算法的基础理论。由于更高层次的相互作用出现在如此多的不同领域，除了研究之外，该奖项还支持多学科研讨会，以及本科生、研究生和博士后水平的教育和培训。该项目正在开发新的算法技术，用于分析和比较张量，以及推进其基本数学理论。研究人员将同构问题作为这个项目的关键试验台，既是理论基础的灵感，也是本身的目标应用。同构问题是指两个给定的对象--无论它们是数据集、拓扑空间、代数组还是张量--尽管呈现方式不同，但具有相同的结构。对于理解张量来说，最有用的性质是对任何两个同构张量都相同的那些性质，因此用于解决张量同构的算法技术与关于张量的基本数学结果之间存在着丰富的相互作用。该项目同时关注张量同构和群同构；这两个问题已经对材料科学、网络分析和量子计算等多个领域产生了影响。这位研究人员运用了一系列数学技术，包括群上同调、代数几何和计算复杂性理论。在这个项目中开发的高阶相互作用理论，以同构问题为试验台，将在从核心计算机科学到复杂自适应系统的广泛领域开辟潜在应用。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Big data is increasingly important in today's world - it not only has the potential to solve critical problems in society, but can also exacerbate or create new problems. Because of this, properly understanding large data sets is a crucial endeavor. Big data sets today are often modeled by a large collection of pairwise interactions - that is, the interactions between two entities, such as people, firms, or molecules. However, such pairwise interactions can miss important phenomena, such as a multi-firm trade deals, one chemical catalyzing the reaction of several others, or a single patent using many technologies. Fortunately, these "higher-order" interactions in big data sets can be accurately modeled using the mathematics of tensors. Tensors are rapidly becoming a fundamental data structure and key mathematical object for the 21st century, much as linear algebra dominated science and engineering for the last 200 years. Tensors are central to a wide range of areas, from fundamental physics to mechanical engineering, from quantum computing to neural networks and deep learning. Within computer science, they arise in cryptography, algorithms for key tasks such as multiplying matrices, and the deepest problems across computer science and mathematics (whether brute-force search algorithms can always be improved, the infamous P versus NP question). The goal of this project is to gain a deeper understanding of the computational properties of tensors, and to develop a foundational theory of the mathematics and algorithmics of beyond-pairwise interactions. Because higher-order interactions arise in so many different areas, in addition to research, this award supports multidisciplinary workshops, as well as education and training at the undergraduate, graduate, and postdoctoral levels.This project is developing new algorithmic techniques for analyzing and comparing tensors, as well as advancing their fundamental mathematical theory. The investigator is using isomorphism problems as a key testbed in this project, both as inspiration for theoretical foundations and as a target application in and of itself. Isomorphism problems ask when two given objects - be they data sets, topological spaces, algebraic groups, or tensors - have the same structure, despite being presented differently. The most useful properties for understanding tensors are those that are the same for any two isomorphic tensors, so there is a rich interplay between algorithmic techniques used to solve tensor isomorphism and foundational mathematical results on tensors. The project is focusing on both tensor isomorphism and group isomorphism; these two problems already have implications for fields as diverse as material science, network analysis, and quantum computing. The investigator is bringing to bear a range of mathematical techniques, including group cohomology, algebraic geometry, and computational complexity theory. The theory of higher-order interactions developed in this project, with isomorphism problems as a testbed, will open up potential applications in a wide variety of areas, from core computer science to complex adaptive systems.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.