AF: Medium: Research in Algorithms and Complexity: Total Functions, Games, and the Brain
AF:媒介:算法和复杂性研究:总体功能、游戏和大脑
基本信息
- 批准号:1763970
- 负责人:
- 金额:$ 120万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-05-01 至 2023-04-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The ubiquitous information environment around us, which has brought to the world unprecedented connectivity and availability of information, as well as newfound opportunities for individual expression, education, work, production and commerce, entertainment, and interpersonal communication, is the result of decades of research in all fields of computer science. Furthermore, our best hope for confronting the many problems this new environment has brought to humanity (privacy and fairness, to mention only two) also lies in new computer science research. Research in theoretical computer science in particular over the past half century has been instrumental in bringing the benefits of Moore's law to bear through fundamental clever algorithms and has made leaps in understanding the capabilities and limitations of computers and their software. In fact, it has articulated one of the most important problems in mathematics and all of science today: is P equal to NP? i.e, is exponential exhaustive search for a solution always avoidable? The two investigators on this award have over the past four decades contributed much to this edifice of mathematical research in computer science, often in close collaboration. In this project, these investigators will work together in order to attack a new generation of problems: complexity questions in the fringe of the P vs. NP problem, a new genre of algorithms possessing a novel kind of robustness, research at the interface between computer science and economics related to income inequality and market efficiency, as well as research aiming at a better understanding of evolution, and of brain functions as basic as memory and as advanced as language. The project will train PhD and Masters students and possibly undergraduates as well on these research topics. The findings of this research will be disseminated to students and researchers, both in computer science and in other disciplines, as well as to the general public, through journal and conference publications, undergraduate and graduate courses, seminars, colloquia, as well as public talks and general interest articles.The project will work on improving our understanding of the complexity of total functions in the class TFNP and its subclasses, in view of recent research progress in that area. On complexity side, the project will: (1) investigate the complexity of an as yet unexplored, from this point of view, Tarski-like fixed-point theorem widely used in economics (2) revisit the approximability of the traveling salesperson problem and (3) explore a new kind of algorithmic notion of robustness based on dense nets of algorithms. In algorithmic game theory, the project will: (1) explore a new variant of the price of anarchy inspired by wealth inequality, as well as the complexity of market equilibria in markets with production and economies of scale (2) research a new game theoretic solution concept based on the topology of dynamical systems (3) pursue the proof of an intriguing new complexity-theoretic conjecture about the inaccessibility of Nash equilibria. The work will also explore certain promising directions at the interface of game theory and learning theory. In the life sciences, the project will explore from the algorithmic point of view the problem of the true nature of mutations, and will extend recent research aiming at the computational understanding of how long-term memory, as well as syntax and language, are achieved in the human brain.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.
我们周围无处不在的信息环境,给世界带来了前所未有的信息连通性和可用性,以及个人表达、教育、工作、生产和商业、娱乐和人际交往的新机会,这是数十年研究的成果在计算机科学的所有领域。此外,我们应对这种新环境给人类带来的许多问题(仅举两个隐私和公平)的最大希望也在于新的计算机科学研究。特别是在过去的半个世纪里,理论计算机科学研究在通过基本的巧妙算法发挥摩尔定律的优势方面发挥了重要作用,并在理解计算机及其软件的功能和局限性方面取得了飞跃。事实上,它阐明了当今数学和所有科学中最重要的问题之一:P 等于 NP 吗?即,对解决方案的指数穷举搜索总是可以避免的吗? 该奖项的两位研究人员在过去四十年中经常密切合作,为计算机科学的数学研究大厦做出了巨大贡献。在这个项目中,这些研究人员将共同努力解决新一代问题:P 与 NP 问题边缘的复杂性问题、具有新颖鲁棒性的新型算法、计算机与计算机之间接口的研究与收入不平等和市场效率相关的科学和经济学,以及旨在更好地理解进化和大脑功能(如记忆等基本功能和语言等高级功能)的研究。 该项目将为博士生和硕士生以及可能的本科生提供有关这些研究主题的培训。这项研究的结果将通过期刊和会议出版物、本科生和研究生课程、研讨会、座谈会以及公开演讲向计算机科学和其他学科的学生和研究人员以及公众传播鉴于该领域的最新研究进展,该项目将致力于提高我们对 TFNP 类及其子类中总函数复杂性的理解。在复杂性方面,该项目将:(1)从这个角度研究尚未探索的类塔斯基不动点定理在经济学中广泛使用的复杂性(2)重新审视旅行商问题的近似性以及( 3)探索一种基于算法密集网络的鲁棒性新算法概念。 在算法博弈论中,该项目将:(1)探索受财富不平等启发的无政府状态价格的新变体,以及具有生产和规模经济的市场中市场均衡的复杂性(2)研究一种新的博弈论基于动力系统拓扑的解决方案概念 (3) 追求关于纳什均衡不可达到的有趣的新复杂性理论猜想的证明。 这项工作还将探索博弈论和学习理论交叉领域的某些有前景的方向。 在生命科学领域,该项目将从算法的角度探讨突变的本质问题,并将扩展近期的研究,旨在通过计算理解如何实现长期记忆以及语法和语言。该奖项反映了 NSF 的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(57)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Recursive stochastic games with positive rewards
具有正奖励的递归随机博弈
- DOI:10.1016/j.tcs.2018.12.018
- 发表时间:2019-07
- 期刊:
- 影响因子:1.1
- 作者:Etessami, Kousha;Wojtczak, Dominik;Yannakakis, Mihalis
- 通讯作者:Yannakakis, Mihalis
Random Projection in the Brain and Computation with Assemblies of Neurons
大脑中的随机投影和神经元集合的计算
- DOI:10.4230/lipics.itcs.2019.57
- 发表时间:2019-01
- 期刊:
- 影响因子:0
- 作者:Papadimitriou; Christos H.
- 通讯作者:Christos H.
The Complexity of Finding S-Factors in Regular Graphs
在正则图中查找 S 因子的复杂性
- DOI:10.4230/lipics.fsttcs.2019.21
- 发表时间:2019-01
- 期刊:
- 影响因子:0
- 作者:Kolisetty, Sanjana;Le, Linh;Volkovich, Ilya;Yannakakis, Mihalis
- 通讯作者:Yannakakis, Mihalis
Passive Static Equilibrium with Frictional Contacts and Application to Grasp Stability Analysis
摩擦接触被动静平衡及其在抓取稳定性分析中的应用
- DOI:10.15607/rss.2018.xiv.064
- 发表时间:2018-06
- 期刊:
- 影响因子:0
- 作者:Haas;Papadimitriou, Christos;Yannakakis, Mihalis;Iyengar, Garud;Ciocarlie, Matei
- 通讯作者:Ciocarlie, Matei
Smoothed complexity of local max-cut and binary max-CSP
局部最大割和二值最大 CSP 的平滑复杂度
- DOI:10.1145/3357713.3384325
- 发表时间:2020-06
- 期刊:
- 影响因子:0
- 作者:Chen, Xi;Guo, Chenghao;Vlatakis;Yannakakis, Mihalis;Zhang, Xinzhi
- 通讯作者:Zhang, Xinzhi
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ 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 - 期刊:
- 影响因子: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 - 期刊:
- 影响因子: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 - 期刊:
- 影响因子: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
A Randomized Phase III Study of Arfolitixorin versus Leucovorin with 5-Fluorouracil, Oxaliplatin, and Bevacizumab for First-Line Treatment of Metastatic Colorectal Cancer: The AGENT Trial
Arfolitixorin 与甲酰四氢叶酸联合 5-氟尿嘧啶、奥沙利铂和贝伐珠单抗一线治疗转移性结直肠癌的随机 III 期研究:AGENT 试验
- DOI:
10.1158/2767-9764.crc-23-0361 - 发表时间:
2024-01-04 - 期刊:
- 影响因子:0
- 作者:
J. Tabernero;T. Yoshino;S. Stintzing;A. de Gramont;P. Gibbs;D. Jonker;Peter Nygren;Christos Papadimitriou;G. Prager;R. Tell;H. Lenz - 通讯作者:
H. Lenz
Christos Papadimitriou的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Christos Papadimitriou', 18)}}的其他基金
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
- 批准号:
2332922 - 财政年份:2024
- 资助金额:
$ 120万 - 项目类别:
Standard Grant
AF: Medium: Research in Algorithms and Complexity for Total Functions
AF:中:全函数的算法和复杂性研究
- 批准号:
2212233 - 财政年份:2022
- 资助金额:
$ 120万 - 项目类别:
Standard Grant
Collaborative Research: Foundations of Deep Learning: Theory, Robustness, and the Brain
协作研究:深度学习的基础:理论、稳健性和大脑 —
- 批准号:
2134059 - 财政年份:2021
- 资助金额:
$ 120万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: A Computational Theory of Brain Function
AF:小:协作研究:脑功能的计算理论
- 批准号:
1910700 - 财政年份:2019
- 资助金额:
$ 120万 - 项目类别:
Standard Grant
AF: Medium: Algorithmic Explorations of Networks, Markets, Evolution, and the Brain
AF:媒介:网络、市场、进化和大脑的算法探索
- 批准号:
1819935 - 财政年份:2017
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant
AF: Medium: Algorithmic Explorations of Networks, Markets, Evolution, and the Brain
AF:媒介:网络、市场、进化和大脑的算法探索
- 批准号:
1408635 - 财政年份:2014
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant
"Succinct Data Representations and Applications
“简洁的数据表示和应用
- 批准号:
1340226 - 财政年份:2013
- 资助金额:
$ 120万 - 项目类别:
Standard Grant
AF: Medium: Algorithmic Research in Game Theory, Networks, and Biology
AF:媒介:博弈论、网络和生物学的算法研究
- 批准号:
0964033 - 财政年份:2010
- 资助金额:
$ 120万 - 项目类别:
Standard Grant
Research on Games, Networks, and Algorithms
博弈、网络和算法研究
- 批准号:
0635319 - 财政年份:2006
- 资助金额:
$ 120万 - 项目类别:
Standard Grant
Research on Algorithms, Complexity, and Database Theory
算法、复杂性和数据库理论研究
- 批准号:
9820897 - 财政年份:1999
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant
相似国自然基金
基于机器学习和经典电动力学研究中等尺寸金属纳米粒子的量子表面等离激元
- 批准号:22373002
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
复合低维拓扑材料中等离激元增强光学响应的研究
- 批准号:12374288
- 批准年份:2023
- 资助金额:52 万元
- 项目类别:面上项目
中等垂直风切变下非对称型热带气旋快速增强的物理机制研究
- 批准号:42305004
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
托卡马克偏滤器中等离子体的多尺度算法与数值模拟研究
- 批准号:12371432
- 批准年份:2023
- 资助金额:43.5 万元
- 项目类别:面上项目
中等红移星系的恒星形成和AGN活动对环境的依赖性研究
- 批准号:
- 批准年份:2022
- 资助金额:55 万元
- 项目类别:面上项目
相似海外基金
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
- 批准号:
2402284 - 财政年份:2024
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402835 - 财政年份:2024
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402836 - 财政年份:2024
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Adventures in Flatland: Algorithms for Modern Memories
合作研究:AF:媒介:平地历险记:现代记忆算法
- 批准号:
2423105 - 财政年份:2024
- 资助金额:
$ 120万 - 项目类别:
Continuing Grant