AF: Medium: Theory of Computation - New Algorithmic and Hardness Techniques

AF：媒介：计算理论 - 新算法和硬度技术

• 批准号: 1900460
• 负责人: Avi Wigderson
• 金额: $ 120万
• 依托单位: Institute For Advanced Study
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-09-01 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1900460&HistoricalAwards=false
• 关键词: AF; Medium; Theory; Computation; New

The goal of this project is developing new theoretical tools for understanding the power and limits of efficient computation. Underlying every computer application, (and indeed computer industry, from networks to security to optimization to storage and so on) available today are ingenious algorithms that utilize the various important resources (time, space, communication) in an efficient manner. However, for not-yet-existing applications (or industries), is their unavailability due to the lack of efficient algorithms that may yet be discovered, or are the underlying problems really intractable, and thus impossible to solve efficiently? This project seeks both new efficient algorithms, as well as new methods for proving intractability. The ideas to be explored by the project use tools and connections to problems from several areas in mathematics, physics and information theory, and promise progress on some of the deepest problems in computational complexity.On the algorithmic side, the project will focus on a wide variety of optimization problems in which the search space has some symmetry. The project will explore algebraic and geometric techniques to analyze both alternating-minimization and geodesic algorithms to solve new problems for which efficient solutions do not yet exist: these include classes of non-convex problems and exponentially large linear programs. On the intractability side, this research will focus on extending a new method of "lifting" hardness results for complex computational models, such as Boolean circuits, proof systems, communication networks and semi-definite programming, from hardness results for much simpler models such as decision trees and polynomials.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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Algorithms for orbit closure separation for invariants and semi-invariants of matrices

矩阵不变量和半不变量的轨道闭合分离算法

• DOI: 10.2140/ant.2020.14.2791
• 发表时间: 2020-01
• 期刊: Algebra & Number Theory
• 影响因子: 1.3
• 作者: Derksen, Harm;Makam, Visu
• 通讯作者: Makam, Visu

On the tensor rank of the 3 x 3 permanent and determinant

关于 3 x 3 常量和行列式的张量秩

• DOI: 10.13001/ela.2021.5107
• 发表时间: 2021-01
• 期刊: The Electronic Journal of Linear Algebra
• 作者: Krishna, Siddharth;Makam, Visu
• 通讯作者: Makam, Visu

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes

非负振幅的非纠缠量子证明的威力

• DOI: 10.1145/3564246.3585248
• 发表时间: 2023-06-02
• 期刊: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: F. G. Jeronimo;Pei Wu
• 通讯作者: Pei Wu

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem

将 Grothendieck 问题的 NP 难度与 Little-Grothendieck 问题分开

• DOI: 10.4230/lipics.itcs.2022.22
• 发表时间: 2022-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Bhattiprolu; Vijay and
• 通讯作者: Vijay and

Almost Sharp Bounds on the Number of Discrete Chains in the Plane

平面上离散链的数量几乎急剧限制

• 发表时间: 2020-06
• 期刊: Proceedings of 36th International Symposium on Computational Geometry (SoCG 2020
• 作者: Frankl, N;Kupavskii, A.
• 通讯作者: Kupavskii, A.