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 问题为模。该项目将解决无法分类的最重要的计算问题，即寻求某种解决方案并且保证该解决方案存在的问题类别。令人惊讶的是，尽管解决方案的存在似乎可以使问题变得容易，但仍有许多此类重要的计算问题无法理解其有效的可解性。此外，相当重要的是，其中一些问题的明显困难在于现代密码学的基础。在 20 世纪 80 年代和 90 年代帮助启动这一研究方向的研究人员将解决该领域中许多新旧的开放性问题。特别是，研究人员将追求一些与总功能相关的开放复杂性问题，包括 Tarski 的复杂性固定点；未分类的组合问题，推广鸽巢原理类 PPP；将总函数与密码学相关的新复杂性问题，以及他们对 APEPP 类的研究中产生的复杂性中的某些基本问题。他们还应探索黑盒算法解决 TFNP 问题的能力和局限性。关键词：算法；复杂;该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Downward Self-Reducibility in TFNP

TFNP 的向下自还原性

DOI：
发表时间：
2023-01
期刊：
14th Innovations in Theoretical Computer Science Conference
影响因子：
0
作者：
Harsha, Prahladh;Mitropolsky, Daniel;Rosen, Alon
通讯作者：
Rosen, Alon

The Smoothed Complexity of Policy Iteration for Markov Decision Processes

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

DOI：
10.1145/3564246.3585220
发表时间：
2023-01
期刊：
In Proceedings of the 55th ACM Symposium on Theory of Computing (STOC
影响因子：
0
作者：
Christ, Miranda;Yannakakis, Mihalis
通讯作者：
Yannakakis, Mihalis

Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP

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

DOI：
发表时间：
2023-01
期刊：
14th Innovations in Theoretical Computer Science Conference
影响因子：
0
作者：
Pasarkar, Amol;Papadimitriou, Christos H.;Yannakakis, Mihalis
通讯作者：
Yannakakis, Mihalis

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

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

DOI：
10.1145/3580507.3597812
发表时间：
2023-07
期刊：
Proceedings of the 24th ACM Conference on Economics and Computation
影响因子：
0
作者：
Papadimitriou, Christos;Vlatakis;Zampetakis, Manolis
通讯作者：
Zampetakis, Manolis

Reducing Tarski to Unique Tarski (In the Black-Box Model

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

DOI：
发表时间：
2023-01
期刊：
38th Computational Complexity Conference
影响因子：
0
作者：
Chen, Xi;Li, Yuhao;Yannakakis, Mihalis
通讯作者：
Yannakakis, Mihalis

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

Christos Papadimitriou其他文献

Novel treatment planning approaches to enhance the therapeutic ratio: targeting the molecular mechanisms of radiation therapy

提高治疗率的新治疗计划方法：针对放射治疗的分子机制

DOI：
10.1007/s12094-019-02165-0
发表时间：
2019-06-28
期刊：
Clinical and Translational Oncology
影响因子：
3.4
作者：
M. Protopapa;V. Kouloulias;A. Kougioumtzopoulou;Z. Liakouli;Christos Papadimitriou;A. Zygogianni
通讯作者：
A. Zygogianni

Neuroscience Needs Network Science

神经科学需要网络科学

DOI：
10.1523/jneurosci.1014-23.2023
发表时间：
2023-08-23
期刊：
The Journal of Neuroscience
影响因子：
0
作者：
Dániel L. Barabási;Ginestra Bianconi;Ed Bullmore;Mark Burgess;SueYeon Chung;Tina Eliassi;Dileep George;István A. Kovács;Hern'an A Makse;T. Nichols;Christos Papadimitriou;Olaf Sporns;Kim Stachenfeld;Zoltán Toroczkai;Emma K. Towlson;A. Zador;Hongkui Zeng;A. Barabási;Amy Bernard;György Buzsáki
通讯作者：
György Buzsáki

IL4/STAT6 Signaling Activates Neural Stem Cell Proliferation and Neurogenesis upon Amyloid-β42 Aggregation in Adult Zebrafish Brain.

IL4/STAT6 信号传导激活成年斑马鱼大脑中淀粉样蛋白-β42 聚集的神经干细胞增殖和神经发生。

DOI：
10.1016/j.celrep.2016.09.075
发表时间：
2016-10-18
期刊：
Cell reports
影响因子：
8.8
作者：
Prabesh Bhattarai;Alvin K. Thomas;M. I. Coşacak;Christos Papadimitriou;Violeta Mashkaryan;Cynthia Froc;S. Reinhardt;T. Kurth;A. Dahl;Yixin Zhang;Caghan Kizil
通讯作者：
Caghan Kizil

Implementing Permutations in the Brain and SVO Frequencies of Languages

在大脑和 SVO 语言频率中实现排列

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
Denis Turcu;Christos Papadimitriou
通讯作者：
Christos Papadimitriou

Identification of peptides in traditional and probiotic sheep milk yoghurt with angiotensin I-converting enzyme (ACE)-inhibitory activity

传统羊奶酸奶和益生菌羊奶酸奶中具有血管紧张素 I 转换酶 (ACE) 抑制活性的肽的鉴定

DOI：
10.1016/j.foodchem.2007.04.028
发表时间：
2024-09-14
期刊：
Food Chemistry
影响因子：
8.8
作者：
Christos Papadimitriou;A. Vafopoulou;Sofia V. Silva;A. Gomes;F. Malcata;E. Alichanidis
通讯作者：
E. Alichanidis