Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications

合作研究：AF：媒介：多项式优化：算法、证书和应用

• 批准号: 2211971
• 负责人: Pravesh Kothari
• 金额: $ 60万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2211971&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Polynomial

Computational problems arising in diverse fields of sciences and engineering can be modeled as optimizing an appropriate objective function subject to a set of constraints. A case of wide interest that captures a surprising array of problems is when the objective function is a polynomial of low-degree. A rich body of theoretical and applied work has led to a fairly extensive understanding of algorithms and hardness for optimizing linear and quadratic functions on domains such as the unit sphere or the hypercube in high dimensions. The situation for polynomials of degree greater than two is, however, not yet well understood. The goal of this project is to advance the frontiers of optimizing higher-degree polynomials in terms of algorithms to estimate and proofs to approximately bound their optima, and then leverage this enhanced understanding in diverse applications. The motivation is both the intrinsic importance of polynomial optimization, as well as several extraneous contexts (constraint satisfaction, graph theory, high-dimensional geometry, proof complexity, and pseudo-randomness, to name a few) where polynomial/tensor optimization arises naturally and could hold the key to further progress. An an example direction, of high importance in modern learning and inference applications, is the generalization of the frequently used principal-component analysis of matrix-valued data to higher-order tensors.This project presents three carefully crafted and intertwined directions to significantly advance the understanding of polynomial optimization. This includes a fresh approach to finding new rounding algorithms that will lead to approximation algorithms with improved guarantees for maximizing cubic and higher-degree polynomials, which in turn is expected to lead to progress beyond longstanding barriers for discrete problems such as Maximum Cut or Small Set Expansion on graphs. The project also involves new approaches towards hardness results for approximate polynomial optimization; currently only very weak bounds are known, and there is a huge gap between the known algorithmic and hardness results. Third, with impetus provided by some recent work by the investigators on refuting constraint-satisfaction problems, the project will embark on a study of polynomial optimization through the lens of certificates on their optima, extending beyond the state of the art linear-algebraic and spectral certificates. Such certificates could have significant ramifications in pseudo-randomness, producing "certified random objects" that are functionally as good as the gold standard (but often highly elusive) explicit constructions. The research and outreach activities of the project will build bridges to allied research communities in algebraic geometry, statistics, operations research, signal processing, and machine learning. The project investigators will train and mentor several graduate students, and also provide engaging research experiences to undergraduates. The research findings will inform graduate level courses on approximate optimization by unifying several problems under the umbrella of polynomial optimization.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.

科学和工程不同领域中出现的计算问题可以建模为在一组约束条件下优化适当的目标函数。一个引起广泛关注的案例是当目标函数是低次多项式时，它捕获了一系列令人惊讶的问题。丰富的理论和应用工作使人们对优化单位球体或高维超立方体等领域的线性和二次函数的算法和硬度有了相当广泛的理解。然而，次数大于二的多项式的情况尚未得到很好的理解。 该项目的目标是在估计和证明近似限制其最优值的算法方面推进优化更高次多项式的前沿，然后在不同的应用中利用这种增强的理解。其动机既是多项式优化的内在重要性，也是多项式/张量优化自然出现并可能成为进一步进展的关键的一些无关上下文（约束满足、图论、高维几何、证明复杂性和伪随机性等）。在现代学习和推理应用中非常重要的一个示例方向是将常用的矩阵值数据主成分分析推广到高阶张量。该项目提出了三个精心设计且相互交织的方向，以显着增进对多项式优化的理解。这包括寻找新舍入算法的新方法，这将导致近似算法具有改进的三次多项式和更高次多项式最大化的保证，这反过来又有望突破离散问题（例如图上的最大割或小集扩展）的长期障碍。该项目还涉及用于近似多项式优化的硬度结果的新方法；目前只知道非常弱的界限，已知的算法和硬度结果之间存在巨大差距。第三，在研究人员最近反驳约束满足问题的一些工作的推动下，该项目将开始通过最优证书的视角来研究多项式优化，超越最先进的线性代数和谱证书。此类证书可能会对伪随机性产生重大影响，产生“经过认证的随机对象”，其功能与金标准（但通常非常难以捉摸）显式构造一样好。该项目的研究和推广活动将为代数几何、统计学、运筹学、信号处理和机器学习领域的联合研究社区搭建桥梁。项目研究人员将培训和指导几名研究生，并为本科生提供引人入胜的研究经验。 研究结果将通过在多项式优化的框架下统一几个问题，为研究生水平的近似优化课程提供信息。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Ellipsoid fitting up to a constant

椭球拟合至常数

• DOI: 10.4230/lipics.icalp.2023.78
• 发表时间: 2023
• 期刊: and Programming (ICALP 2023
• 作者: Hsieh, Jun-Ting;Kothari, Pravesh K.;Potechin, Aaron;Xu, Jeff
• 通讯作者: Xu, Jeff

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

来自半随机 CSP 反驳的 3 查询本地可解码代码的近三次下界

• DOI: 10.1145/3564246.3585143
• 发表时间: 2023
• 期刊: STOC
• 作者: Alrabiah, Omar;Guruswami, Venkatesan;Kothari, Pravesh K.;Manohar, Peter
• 通讯作者: Manohar, Peter

Algorithms Approaching the Threshold for Semi-random Planted Clique

接近半随机植入派系阈值的算法

• DOI: 10.1145/3564246.3585184
• 发表时间: 2023
• 期刊: STOC
• 作者: Buhai, Rares-Darius;Kothari, Pravesh K.;Steurer, David
• 通讯作者: Steurer, David