Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications
合作研究:AF:媒介:多项式优化:算法、证书和应用
基本信息
- 批准号:2211971
- 负责人:
- 金额:$ 60万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2022
- 资助国家:美国
- 起止时间:2022-06-15 至 2026-05-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
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的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(3)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Ellipsoid fitting up to a constant
椭球拟合至常数
- DOI:10.4230/lipics.icalp.2023.78
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者: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
- 期刊:
- 影响因子:0
- 作者: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
- 期刊:
- 影响因子:0
- 作者:Buhai, Rares-Darius;Kothari, Pravesh K.;Steurer, David
- 通讯作者:Steurer, David
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Pravesh Kothari其他文献
Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions
ℓ1 逼近的紧界和自界函数的学习
- DOI:
- 发表时间:
2014 - 期刊:
- 影响因子:0
- 作者:
V. Feldman;Pravesh Kothari;J. Vondrák - 通讯作者:
J. Vondrák
Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
多项式时间平方和可以稳健地估计高斯函数的均值和协方差
- DOI:
- 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Pravesh Kothari;Peter Manohar;Brian Zhang - 通讯作者:
Brian Zhang
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures
高斯和其他非球形混合物的异常值稳健聚类
- DOI:
- 发表时间:
2020 - 期刊:
- 影响因子:0
- 作者:
Ainesh Bakshi;Ilias Diakonikolas;Samuel B. Hopkins;D. Kane;Sushrut Karmalkar;Pravesh Kothari - 通讯作者:
Pravesh Kothari
A simple and sharper proof of the hypergraph Moore bound
超图摩尔界的简单而清晰的证明
- DOI:
10.48550/arxiv.2207.10850 - 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Jun;Pravesh Kothari;Sidhanth Mohanty - 通讯作者:
Sidhanth Mohanty
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method
公钥加密、本地伪随机生成器和低次方法
- DOI:
- 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Andrej Bogdanov;Pravesh Kothari;Alon Rosen - 通讯作者:
Alon Rosen
Pravesh Kothari的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Pravesh Kothari', 18)}}的其他基金
CAREER: The Nature of Average-Case Computation
职业:平均情况计算的本质
- 批准号:
2422342 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Continuing Grant
CAREER: The Nature of Average-Case Computation
职业:平均情况计算的本质
- 批准号:
2047933 - 财政年份:2021
- 资助金额:
$ 60万 - 项目类别:
Continuing Grant
相似国自然基金
Research on Quantum Field Theory without a Lagrangian Description
- 批准号:24ZR1403900
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
Cell Research
- 批准号:31224802
- 批准年份:2012
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research
- 批准号:31024804
- 批准年份:2010
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Cell Research (细胞研究)
- 批准号:30824808
- 批准年份:2008
- 资助金额:24.0 万元
- 项目类别:专项基金项目
Research on the Rapid Growth Mechanism of KDP Crystal
- 批准号:10774081
- 批准年份:2007
- 资助金额:45.0 万元
- 项目类别:面上项目
相似海外基金
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402836 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402851 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
- 批准号:
2402283 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Continuing Grant