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的理解，在此过程中找到新的算法和/或下限。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.