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

该项目的目标是开发新的理论工具，以了解高效计算的能力和局限性。当今可用的每一个计算机应用程序（实际上是计算机行业，从网络到安全到优化到存储等）都是巧妙的算法，这些算法以有效的方式利用各种重要资源（时间，空间，通信）。然而，对于尚未存在的应用程序（或行业），它们的不可用是由于缺乏可能尚未发现的有效算法，还是底层问题确实难以解决，因此无法有效解决？这个项目寻求新的有效算法，以及证明棘手的新方法。该项目将利用数学、物理学和信息论等领域的工具和问题的联系来探索这些想法，并有望在计算复杂性的一些最深层次问题上取得进展。在算法方面，该项目将专注于搜索空间具有一定对称性的各种优化问题。该项目将探索代数和几何技术来分析交替最小化和测地线算法，以解决尚不存在有效解决方案的新问题：这些问题包括非凸问题和指数大型线性规划。在棘手的方面，这项研究将集中在扩展一个新的方法，“提升”硬度结果的复杂计算模型，如布尔电路，证明系统，通信网络和半定规划，该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识产权进行评估来支持。优点和更广泛的影响审查标准。

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.