权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。