Algebraic Proof Systems, Convexity, and Algorithms

This project tackles some of the central questions in algorithms, optimization, and the theory of machine learning, through the lens of the "Sum of Squares" algorithmic framework. In particular, it will allow us to understand what classes of functions can be efficiently minimized, and what computational resources are needed to do so. If successful, this will significantly advance our understanding in all these key areas, produce new practical algorithmic methodologies, as well as build new connections with other fields, including quantum information theory, statistical physics, extremal graph theory and more.

This collaborative grant will foster new interactions between intellectual communities that have had relatively little interaction so far, and the PIs will organize workshops, courses, and other events that bring these communities together. The students and postdocs trained will gain a uniquely broad view of the landscape of these areas.

The PIs propose a unified approach to the development and analysis of convex proof systems that include and generalize the "Sum of Squares" (SoS) method. Despite considerable recent progress, understanding SoS?s performance seems to be out-of-reach for most current techniques. Significant progress in this area requires the synthesis of ideas and techniques from different domains, including theoretical computer science, optimization, algebraic geometry, quantum information theory and machine learning. The research plans include both theory-building and problem-solving aspects, with the ultimate goal of obtaining a complete understanding of the SoS method and related proof systems, as well as their algorithmic implications.

Research efforts will be directed along several thrusts: Unique Games and related problems (Small Set Expansion, Max Cut, Sparsest Cut), analysis of average-case problems (e.g., Planted Clique), applications to Machine Learning (sparse PCA, dictionary learning), algorithmic speedups of SoS, and connections to math and physics (e.g., quantum entanglement, p-spin glasses, extremal graph theory and algebraic geometry). While the main focus is on theoretical aspects, this project is also concerned with effective computational methods, and the outcomes may yield novel practical techniques for machine learning and optimization.

Other key features of this proposal include its strong integration with curriculum development, undergraduate research projects, and training the next wave of graduate students and postdocs and equipping them with the necessary tools to work across these areas.