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

点击翻译按钮获取中文摘要

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.