CAREER: Higher-Order Interactions in Tensors and Isomorphism Problems

职业：张量和同构问题中的高阶相互作用

• 批准号: 2047756
• 负责人: Joshua Grochow
• 金额: $ 60万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-03-15 至 2026-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2047756&HistoricalAwards=false
• 关键词: CAREER; Higher; Order; Interactions; Tensors

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.

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

项目成果

Comer Schemes, Relation Algebras, and the Flexible Atom Conjecture

角点方案、关系代数和灵活原子猜想

• 发表时间: 2023
• 期刊: Relational and Algebraic Methods in Computer Science. RAMiCS 2023
• 作者: Alm, J.F.

Matrix Multiplication via Matrix Groups

通过矩阵组进行矩阵乘法

• 发表时间: 2023
• 期刊: Leibniz international proceedings in informatics
• 作者: Blasiak, Jonah;Cohn, Henry;Grochow, Joshua A.;Pratt, Kevin;Umans, Chris
• 通讯作者: Umans, Chris

Leibniz International Proceedings in Informatics (LIPIcs):15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

莱布尼茨国际信息学会议录 (LIPIcs)：第 15 届理论计算机科学创新会议 (ITCS 2024)

• DOI: 10.4230/lipics.itcs.2024.16
• 发表时间: 2024
• 期刊: Leibniz international proceedings in informatics
• 作者: Blackwell, Keller;Wootters, Mary
• 通讯作者: Wootters, Mary

Experience Report: Standards-Based Grading at Scale in Algorithms

经验报告：算法中基于标准的大规模分级

• DOI: 10.1145/3502718.3524750
• 发表时间: 2022
• 期刊: 27th ACM Conference on on Innovation and Technology in Computer Science Education
• 作者: Chen, Lijun;Grochow, Joshua A.;Layer, Ryan;Levet, Michael
• 通讯作者: Levet, Michael

Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

莱布尼茨国际信息学会议录 (LIPIcs)：第 38 届计算复杂性会议 (CCC 2023)

• DOI: 10.4230/lipics.ccc.2023.14
• 发表时间: 2023
• 期刊: 38th Computational Complexity Conference (CCC 2023
• 作者: Block, Alexander R.;Blocki, Jeremiah;Cheng, Kuan;Grigorescu, Elena;Li, Xin;Zheng, Yu;Zhu, Minshen
• 通讯作者: Zhu, Minshen