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.

为实际计算问题寻找有效的算法从近80年前开始就定义了计算机科学。 同样重要的是寻找棘手性，也就是说，确定某些计算任务不能有效地解决。在过去的半个世纪里，NP完全性的重要概念在将实际问题分为易处理的和难处理的方面取得了很大的进展，模是尚未解决的P vs NP问题。 这个项目将解决最重要的机构的计算问题，不能这样分类，即一类问题，其中寻求某种解决方案，解决方案是保证存在的。 令人惊讶的是，即使存在一个解决方案可能会出现使问题容易，有许多重要的计算问题，这类有效的可解性是不理解的。 此外，相当重要的是，其中一些问题的明显困难在于现代密码学的基础。 研究人员在20世纪80年代和90年代帮助启动了这一研究路线，他们将解决这一领域的许多新老开放问题。特别是，研究人员将研究一些与全函数相关的开放复杂性问题，包括塔斯基不动点的复杂性;未分类的组合问题，推广鸽子洞原理类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

Reducing Tarski to Unique Tarski (in the Black-box Model)

将 Tarski 简化为独特的 Tarski（在黑盒模型中）

• DOI: 10.4230/lipics.ccc.2023.21
• 发表时间: 2023
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: Xi Chen;Yuhao Li;M. Yannakakis
• 通讯作者: M. Yannakakis

Downward Self-Reducibility in TFNP

TFNP 的向下自还原性

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

Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP

极值组合、迭代鸽笼论证以及 PPP 的推广

• DOI: 10.48550/arxiv.2209.07625
• 发表时间: 2022
• 期刊: ArXiv
• 作者: Amol Pasarkar;M. Yannakakis;Christos Papadimitriou
• 通讯作者: Christos Papadimitriou

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