Project Grant 2233897

The Massachusetts Institute of Technology (MIT) received a $531,494 Project Grant award from the National Science Foundation Division of Computing and Communication Foundations on May 1, 2023 to complete work by April 30, 2026.

Under this award, MIT will conduct research investigating low-degree methods for optimization in random structures and their potential and limitations. Specifically, MIT aims to verify if low-degree method-based algorithms can achieve state-of-the-art performance across a range of problems, identify potential computational advantages, and establish the limits of what these approaches can achieve. Key problems to be examined include finding the largest clique in Erdos-Renyi random graphs, sparse linear regression, and satisfying assignments for random constraint satisfaction problems. MIT will also explore establishing barriers for low-degree method-based algorithms in high-dimensional statistical inference models exhibiting known computation gaps, such as through overlap gap property methodology. This award supports the Computer and Information Science and Engineering program's goal of advancing computing and communications research.