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.

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