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.