AF: Medium: Research in Algorithms and Complexity for Total Functions

AF：中：全函数的算法和复杂性研究

• 批准号: 2212233
• 负责人: Christos Papadimitriou
• 金额: $ 60万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212233&HistoricalAwards=false
• 关键词: AF; Medium; Research; Algorithms; Complexity

Finding efficient algorithms for practical computational problems has defined computer science from its beginnings almost eight decades ago. Equally fundamental has been the search for intractability, that is, establishing that certain computational tasks cannot be solved efficiently. The important concept of NP-completeness has come a long way over the past half century in classifying practical problems into tractable and intractable, modulo the yet unresolved P vs NP question. This project will address the most important body of computational problems which cannot be so classified, namely the class of problems in which a solution of certain kind is sought, and the solution is guaranteed to exist. Surprisingly, even though the existence of a solution may appear to render a problem easy, there are many important computational problems of this sort for which efficient solvability is not understood. In addition, and quite importantly, the apparent difficulty of some of these problems lies at the foundations of modern Cryptography. The investigators, who helped initiate this line of research in the 1980s and 1990s, will address many old and new open questions in this field.In particular, the investigators shall pursue a number of open complexity questions related to total functions including the complexity of Tarski fixpoints; unclassified combinatorial problems, generalizing the pigeonhole principle class PPP; new complexity problems relating total functions with Cryptography, as well as certain fundamental problems in Complexity that arose from their study of the class APEPP. They shall also explore the power and limitations of black box algorithms for TFNP problems. Keywords: Algorithms; complexity; total functions.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.

为实践计算问题找到有效的算法已经从近八十年前的一开始就定义了计算机科学。 同样基本的是寻找难治性，也就是说，确定无法有效地解决某些计算任务。在过去的半个世纪中，NP完整性的重要概念在将实际问题分类为易于处理且棘手的，模仿尚未解决的P与NP问题方面已经走了很长一段路。 该项目将解决无法分类的最重要的计算问题体系，即寻求某种解决方案的问题类别，并保证解决方案存在。 令人惊讶的是，即使解决方案的存在似乎使问题变得容易，但此类计算问题存在许多重要的计算问题。 此外，很重要的是，其中一些问题的明显困难在于现代密码学的基础。 在1980年代和1990年代帮助启动这一研究的研究人员将解决该领域的许多新旧问题。尤其是，调查人员应提出许多与总体功能有关的开放复杂性问题，包括Tarski Fixpoint的复杂性；未分类的组合问题，概括了PIGONHOLE原理PPP；将总功能与密码学有关的新复杂性问题，以及对APEPP类的研究引起的某些复杂性的基本问题。他们还应探讨黑匣子算法在TFNP问题上的功能和局限性。 关键字：算法；复杂;总功能。该奖项反映了NSF的法定任务，并通过使用基金会的知识分子优点和更广泛的影响审查标准来评估值得支持。

项目成果

The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points

多人凹博弈和角谷不动点的计算复杂度

• DOI: 10.1145/3580507.3597812
• 发表时间: 2023
• 期刊: Proceedings of the 24th ACM Conference on Economics and Computation
• 作者: Papadimitriou, Christos;Vlatakis-Gkaragkounis, Emmanouil-Vasileios;Zampetakis, Manolis
• 通讯作者: Zampetakis, Manolis

The Smoothed Complexity of Policy Iteration for Markov Decision Processes

马尔可夫决策过程的策略迭代的平滑复杂度

• DOI: 10.1145/3564246.3585220
• 发表时间: 2023
• 期刊: In Proceedings of the 55th ACM Symposium on Theory of Computing (STOC
• 作者: Christ, Miranda;Yannakakis, Mihalis
• 通讯作者: Yannakakis, Mihalis

Downward Self-Reducibility in TFNP

TFNP 的向下自还原性

• 发表时间: 2023
• 期刊: 14th Innovations in Theoretical Computer Science Conference
• 作者: Harsha, Prahladh;Mitropolsky, Daniel;Rosen, Alon
• 通讯作者: Rosen, Alon