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

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

• 批准号: 2211972
• 负责人: Venkatesan Guruswami
• 金额: $ 60万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2211972&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.

在科学和工程领域中产生的计算问题可以建模为优化适当的目标功能，但受一组约束的约束。引起令人惊讶的问题的广泛兴趣的情况是，当目标函数是低度的多项式时。丰富的理论和应用工作已经使人们对算法和硬度有了相当广泛的了解，以优化诸如单位球体或高维度的域上的线性和二次功能。但是，程度大于两个的多项式的情况尚不清楚。 该项目的目的是通过算法来促进优化高度多项式的前沿，以估算和证明大致约束其Optima，然后利用对不同应用程序的增强理解。动机既是多项式优化的固有重要性，也是多种无关的环境（约束满意度，图形理论，高维几何形状，证明复杂性和伪随机性，仅举几例），在多项式/张量优化的情况下，可以自然出现，并且可以保持关键以进一步进步。在现代学习和推理应用中非常重要的一个示例方向是对矩阵值数据对高阶张量的经常使用的主组件分析的概括。此项目提出了三个精心设计和相互交织的方向，以显着提高对多项式优化的理解。这包括一种新的方法来找到新的圆形算法，该算法将导致近似算法，并提供改进的保证，以最大程度地提高立方和更高的多项式，这反过来又预计这将导致超越长期障碍的离散问题，例如最大值剪切或图表上的小型集合。该项目还涉及用于近似多项式优化的硬度结果的新方法。目前，只有非常弱的界限，并且已知的算法和硬度结果之间存在巨大差距。第三，随着研究人员最近在反驳约束满足问题方面提供的一些动力，该项目将通过其Optima上的证书镜头进行多项式优化的研究，并超越了最先进的线性地倾向和频谱证书。这样的证书可能会在伪随机上产生重大影响，从而产生“经过认证的随机对象”，在功能上与黄金标准（但通常难以捉摸的）显式结构一样好。该项目的研究和外展活动将在代数几何，统计，操作研究，信号处理和机器学习中与盟军研究社区建造桥梁。项目调查人员将培训和指导几位研究生，并为大学生提供引人入胜的研究经验。 该研究结果将通过在多项式优化的保护下统一几个问题来为研究生级别的课程提供近似优化的信息。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的评估来评估值得支持的。

项目成果

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

绕过 XOR 技巧：超图团数的更强证书

• 发表时间: 2022
• 期刊: and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022
• 作者: Guruswami, Venkatesan;Kothari, Pravesh K.;Manohar, Peter
• 通讯作者: Manohar, Peter

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

• DOI: 10.1145/3519935.3519955
• 发表时间: 2021-09
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: V. Guruswami;Pravesh Kothari;Peter Manohar

Quickly-Decodable Group Testing with Fewer Tests: Price–Scarlett’s Nonadaptive Splitting with Explicit Scalars

用更少的测试进行快速解码的组测试：Price-Scarlett-带有显式标量的非自适应分割

• DOI: 10.1109/isit54713.2023.10206843
• 发表时间: 2023
• 期刊: IEEE
• 作者: Wang, Hsin-Po;Gabrys, Ryan;Guruswami, Venkatesan
• 通讯作者: Guruswami, Venkatesan

Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ p Norms

全域最小距离问题和全-p范数中最短向量问题的参数化不可逼近性

• DOI: 10.1145/3564246.3585214
• 发表时间: 2023
• 期刊: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: Bennett, Huck;Cheraghchi, Mahdi;Guruswami, Venkatesan;Ribeiro, João
• 通讯作者: Ribeiro, João