CAREER: Higher-Order Interactions in Tensors and Isomorphism Problems

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

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.