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