AF: Large: Collaborative Research: Algebraic Proof Systems, Convexity, and Algorithms

该项目通过“平方和”算法框架解决了算法、优化和机器学习理论中的一些核心问题。特别是，它将允许我们了解哪些函数类可以有效地最小化，以及这样做需要哪些计算资源。如果成功，这将极大地推进我们对所有这些关键领域的理解，产生新的实用算法方法，并与其他领域建立新的联系，包括量子信息论、统计物理学、极值图论等。这项合作奖助金将促进迄今为止相对较少互动的知识分子社区之间的新互动，而pi将组织研讨会、课程和其他活动，将这些社区聚集在一起。接受培训的学生和博士后将获得这些地区独特的广阔视野。pi提出了一种统一的方法来开发和分析凸证明系统，其中包括并推广了“平方和”（so）方法。尽管最近取得了相当大的进展，但理解SoS？S的性能似乎是目前大多数技术无法企及的。这一领域的重大进展需要综合不同领域的思想和技术，包括理论计算机科学、优化、代数几何、量子信息理论和机器学习。研究计划包括理论构建和问题解决两个方面，最终目标是全面了解SoS方法和相关证明系统，以及它们的算法含义。研究工作将沿着几个方向进行：独特的游戏和相关问题（小集扩展，最大切割，最稀疏切割），平均情况问题的分析（例如，植团），机器学习的应用（稀疏PCA，字典学习），SoS的算法加速，以及与数学和物理的联系（例如，量子纠缠，p自旋玻璃，极值图论和代数几何）。虽然主要侧重于理论方面，但该项目也涉及有效的计算方法，其结果可能会产生用于机器学习和优化的新颖实用技术。该提案的其他关键特征包括与课程开发、本科研究项目、培养下一波研究生和博士后并为他们提供必要的工具来跨这些领域工作的强大整合。

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.