权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

AF：小：平方和层次结构的进一步研究

基本信息

批准号：
2008920
负责人：
Aaron Potechin
金额：
$ 40万
依托单位：
University of Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008920&HistoricalAwards=false
关键词：
AF SMALL Further Investigation Sum

项目摘要

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.

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

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

对称二次函数的 SoS 认证及其与约束布尔超立方优化的联系

DOI：
发表时间：
2021
期刊：
ICALP 2021
影响因子：
0
作者：
Kurpisz, Adam;Potechin, Aaron;Wirth, Elias Samuel
通讯作者：
Wirth, Elias Samuel

Sum-of-Squares Lower Bounds for Sparse Independent Set

稀疏独立集的平方和下界

DOI：
10.1109/focs52979.2021.00048
发表时间：
2022
期刊：
FOCS 2021
影响因子：
0
作者：
Jones, Chris;Potechin, Aaron;Rajendran, Goutham;Tulsiani, Madhur;Xu, Jeff
通讯作者：
Xu, Jeff

The Sixth Moment of Random Determinants

随机行列式的六阶矩

DOI：
发表时间：
2023
期刊：
Journal of integer sequences
影响因子：
0.5
作者：
Beck, Dominik;Lv, Zelin;Potechin, Aaron
通讯作者：
Potechin, Aaron

Sum-of-Squares Lower Bounds for Densest k-Subgraph

最稠 k 子图的平方和下界

DOI：
10.1145/3564246.3585221
发表时间：
2023
期刊：
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
影响因子：
0
作者：
Jones, Chris;Potechin, Aaron;Rajendran, Goutham;Xu, Jeff
通讯作者：
Xu, Jeff

Separating MAX 2-AND, MAX DI-CUT and MAX CUT

分离 MAX 2-AND、MAX DI-CUT 和 MAX CUT