CAREER: Tensor Ranks and Regularity Methods in Combinatorics

Linear algebra – the theory of linear equations, vectors, and matrices – is foundational not only to modern mathematics but also to science and technology, with applications from medical research to smartphones to machine learning. Nonetheless, most complex problems involve interactions among three or more variables and are thus not fully captured by (two-dimensional) matrices. Researchers therefore often flatten multidimensional phenomena into linear approximations in order to utilize available mathematical methods. Excitingly, multiple results from recent years hint at the possibility of a true higher-order analogue of linear algebra anchored by new notions of rank for tensors (higher-dimensional matrices); indeed, replacing the classical definition of tensor rank from the 1920s by slice rank, a relaxed and arguably more natural notion, has already proven key in several breakthroughs. Given the ubiquity of tensors, a more complete theory of tensor ranks would yield downstream applications in myriad areas of math and theoretical computer science. New tensor rank methods also pave the way for advancements in areas of science and technology that use linear algebra; especially timely is the link to machine learning, where a more relaxed notion of tensor rank could improve the efficiency of tensor decompositions, which are important in classical machine learning and which could gain new relevance for transformative technologies like large language models. This project centers on developing the theory and applications of tensor ranks, including by research into both long-standing and novel questions in math and computer science, by teaching and creating educational materials about tensor ranks, and by organizing the first research workshop on these topics. The project has three main research objectives. The first objective is to establish new approaches to fundamental questions in additive combinatorics and higher-order Fourier analysis, particularly by using recent advances around the partition-vs-analytic rank conjecture and new, weak regularity lemmas in order to make progress towards the Polynomial Gowers Inverse conjecture. The second objective focuses on expanding applications of tensor ranks to new areas, especially in computer science (communication complexity and computational complexity). Problems here involve a log-rank conjecture for tensors, hypergraph coloring, and approximation algorithms for tensor ranks. The third objective, spanning multilinear algebra and graph theory, aims to further develop the theory of tensor ranks by proving new relations between existing tensor rank notions; improving bounds on the ranks of the determinant, permanent, and other well-studied multilinear polynomials; and further developing surprising ties with the dependent random choice method in (hyper)graph theory. The project also includes several initiatives of broader impact: developing curricula on early steps in research that can be shared and implemented at other institutions, creating opportunities for undergraduate and graduate research into tensor ranks, and fostering multidisciplinary research collaborations. 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. NSF Award ID: 2544490 | Program: 01003031DB NSF RESEARCH & RELATED ACTIVIT,01002930DB NSF RESEARCH & RELATED ACTIVIT,01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Guy Moshkovitz | Institution: CUNY Baruch College, NEW YORK, NY | Award Amount: $262,854 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2544490 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2544490.html