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.

该项目的目标是开发新的理论工具，以了解有效计算的功能和限制。今天可用的每个计算机应用程序（实际上是从网络到优化再到存储等）的基础是巧妙的算法，它们以有效的方式利用了各种重要资源（时空，空间，通信）。但是，对于尚不存在的应用程序（或行业），由于缺乏有效的算法而无法发现的，它们是否可能被发现，还是潜在的问题真的很棘手，因此无法有效地解决？该项目既寻求新​​的有效算法，也寻求证明棘手性的新方法。项目使用工具和连接到数学，物理和信息理论的几个领域的问题，并有望在计算复杂性中一些最深切的问题上进行进展。在算法方面，该项目将集中在搜索空间具有一定的对称性的各种优化问题上。该项目将探索代数和几何技术，以分析交替的最小化和地理算法，以解决有效解决方案尚不存在的新问题：这些问题包括非convex问题的类别和指数性的大型线性程序。在顽固性方面，这项研究将着重于扩展一种新的方法来为复杂的计算模型（例如布尔电路，证明系统，通讯网络和半定义编程）等新方法，从更简单的模型中的硬度结果，例如决策树和多种措施等诸如NSF的法定任务和构成的范围，从而构成了更简单的模型，这表明了NSF的法规及其范围的范围。 标准。

项目成果

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

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

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

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

• DOI: 10.1109/focs46700.2020.00011
• 发表时间: 2020-01
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Or Meir;Jakob Nordström;T. Pitassi;Robert Robere;Susanna F. de Rezende

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes

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

KRW Composition Theorems via Lifting

• DOI: 10.1109/focs46700.2020.00013
• 发表时间: 2020-07
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Susanna F. de Rezende;Or Meir;Jakob Nordström;T. Pitassi;Robert Robere

Extremely Deep Proofs

极其深刻的证明

• DOI: 10.4230/lipics.itcs.2022.70
• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Fleming, Noah and