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.
