AF: SMALL: Further Investigation of the Sum of Squares Hierarchy

平方和层次(SOS)是一个算法框架，它具有以下良好的性质。首先，SOS具有广泛的适用性和惊人的强大功能，它捕获了许多问题的最著名的算法。其次，在某种意义上，SOS很简单，因为它所使用的只是多项式等式和平方是非负的事实。因此，了解SOS的力量可以让我们深入了解如何设计新的算法，并深入了解哪些问题无法有效解决。在这个项目中，调查者将进一步研究SOS的力量。作为这个项目的一部分，调查员将在复杂性理论研究方面培训和指导研究生。为了进一步调查SOS的力量，调查员计划研究包括但不限于以下问题。(1)一个约束满足问题的2次SOS下界能提升到更高的SOS下界吗？这个问题与确定SOS在独特游戏问题上的表现有关，这是一个重大的开放问题。(2)当对手破坏了一小部分输入时，SOS在稳健估计问题上的性能如何？(3)图矩阵是分析SOS时出现的一种矩阵。然而，图矩阵在数学上并没有得到很好的理解，因为图矩阵上只有粗略的范数界。图矩阵上的这些范数界可以改进吗？更有野心的是，人们能确定图矩阵的特征值和/或奇异值的谱吗？(4)人们能不能消除当前对种植问题的SOS分析技术的限制，这些问题是试图区分信号和随机噪声的问题？(5)SOS在寻找张量的张量核范数方面的性能如何？这个问题与SOS在张量分解和张量补全问题上的表现密切相关，张量分解和张量补全是机器学习中的两个重要问题。通过研究这些问题，研究人员旨在进一步提高对SOS的理解，寻找新的算法和/或下限。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The sum of squares hierarchy (SOS) is an algorithmic framework which has the following nice properties. First, SOS is broadly applicable and surprisingly powerful, capturing the best-known algorithms for many problems. Second, in some sense, SOS is simple as all it uses is polynomial equalities and the fact that squares are non-negative. Thus, understanding the power of SOS gives us insights into designing new algorithms and insights into which problems cannot be solved efficiently. In this project, the investigator will further investigate the power of SOS. As part of this project, the investigator will train and mentor graduate students in complexity-theory research.To further investigate the power of SOS, the investigator plans to research questions including but not limited to the following. (1) Can one lift degree 2 SOS lower bounds for constraint satisfaction problems to higher degree SOS lower bounds? This question is related to determining the performance of SOS on the unique games problem, which is a major open problem. (2) What is the performance of SOS on robust estimation problems where an adversary has corrupted a small portion of the input? (3) Graph matrices are a type of matrix that appears when analyzing SOS. However, graph matrices are not well understood mathematically as there are only rough norm bounds on graph matrices. Can these norm bounds on graph matrices be improved? More ambitiously, can one determine the spectrum of the eigenvalues and/or singular values of graph matrices? (4) Can one remove the current limitations on techniques for analyzing SOS on planted problems, which are problems where trying to distinguish a signal from random noise? (5) What is the performance of SOS for finding the tensor nuclear norm of a tensor? This question is closely related to the performance of SOS on the tensor decomposition and tensor completion problems, which are two important problems in machine learning. Through researching these questions, the investigator aims to further improve the understanding of SOS, finding new algorithms and/or lower bounds along the way.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.