AF: Medium: Research in Algorithms and Complexity: Total Functions, Games, and the Brain

AF：媒介：算法和复杂性研究：总体功能、游戏和大脑

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

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)调查一个尚未被探索的复杂性，从这个角度来看，Tarski-like不动点定理在经济学中广泛使用；(2)重新审视旅行销售人员问题的近似性；(3)探索一种新的基于密集算法网络的鲁棒性算法概念。在算法博弈论方面，该项目将：(1)探索受财富不平等启发的无政府状态价格的新变体，以及具有生产和规模经济的市场中市场均衡的复杂性；(2)研究基于动态系统拓扑的新博弈论解决概念；(3)追求一个关于纳什均衡不可达性的有趣的新复杂性理论猜想的证明。本工作还将在博弈论和学习理论的界面上探索一些有前途的方向。在生命科学方面，该项目将从算法的角度探索突变的真实本质问题，并将扩展最近的研究，旨在通过计算理解长期记忆、语法和语言是如何在人脑中实现的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Planar graphs that need four pages

需要四页的平面图

• DOI: 10.1016/j.jctb.2020.05.008
• 发表时间: 2020
• 期刊: Series B
• 作者: Yannakakis, Mihalis

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations

分支马尔可夫决策过程的多项式时间算法和概率最小（最大）多项式贝尔曼方程

• DOI: 10.1287/moor.2018.0970
• 发表时间: 2020
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: Etessami, Kousha;Stewart, Alistair;Yannakakis, Mihalis
• 通讯作者: Yannakakis, Mihalis

No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix

无悔学习和混合纳什均衡：它们不能混合

• 发表时间: 2020
• 期刊: Annual Conference on Neural Information Processing Systems
• 作者: Vlatakis-Gkaragkounis, Emmanouil-Vasileios;Flokas, Lampros;Mertikopoulos, Panayotis;Piliouras, Georgios
• 通讯作者: Piliouras, Georgios

Fixed Point Computation Problems and Facets of Complexity

定点计算问题和复杂性的各个方面

• DOI: 10.4230/lipics.icalp.2019.5
• 发表时间: 2019
• 期刊: and Programming
• 作者: Yannakakis, Mihalis

Epinoia: Intent Checker for Stateful Networks

Epinoia：状态网络的意图检查器

• DOI: 10.1109/icccn52240.2021.9522299
• 发表时间: 2021
• 期刊: International Conference on Computer Communications and Networks
• 作者: Wang, Huazhe;Sharma, Puneet;Ahmed, Faraz;Kang, Joon-Myung;Qian, Chen;Yannakakis, Mihalis
• 通讯作者: Yannakakis, Mihalis