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

我们周围无处不在的信息环境给世界带来了前所未有的信息连通性和可用性，以及个人表达、教育、工作、生产和商业、娱乐以及人际交流的新机会，这是计算机科学所有领域数十年研究的结果。此外，我们应对这个新环境给人类带来的许多问题（隐私和公平，仅举两例）的最大希望也在于新的计算机科学研究。特别是在过去的半个世纪里，理论计算机科学的研究有助于通过基本的聪明算法来实现摩尔定律的好处，并在理解计算机及其软件的能力和局限性方面取得了飞跃。事实上，它阐明了数学和当今所有科学中最重要的问题之一：P等于NP吗？即，指数穷举搜索解总是可以避免的吗？ 在过去的四十年里，该奖项的两位研究人员为计算机科学中的数学研究做出了很大贡献，通常是密切合作。在这个项目中，这些研究人员将共同努力，以解决新一代的问题：NP问题边缘的复杂性问题，一种具有新型鲁棒性的新型算法，计算机科学与经济学之间关于收入不平等和市场效率的界面研究，以及旨在更好地理解进化的研究，以及大脑的基本功能如记忆和高级功能如语言。 该项目将对博士生和硕士生以及可能的本科生进行这些研究课题的培训。本研究的结果将通过期刊和会议出版物、本科生和研究生课程、研讨会、学术讨论会以及公众讲座和一般兴趣文章传播给计算机科学和其他学科的学生和研究人员以及公众。该项目将致力于提高我们对TFNP类及其子类中总函数复杂性的理解，考虑到该领域最近研究进展，在复杂性方面，该项目将：（1）研究尚未探索的复杂性，从这个角度来看，广泛应用于经济学的Tarski型不动点定理（2）重新审视旅行推销员问题的近似性，以及（3）探索基于算法密集网的鲁棒性的新算法概念。 在算法博弈论中，该项目将：（1）探索由财富不平等引发的无政府状态的代价的新变体，以及在具有生产和规模经济的市场中市场均衡的复杂性（2）研究基于动态系统拓扑的新博弈论解决方案概念（3）追求一个有趣的新复杂性的证明-关于纳什均衡不可达性的理论猜想。 这项工作还将探索在博弈论和学习理论的接口某些有前途的方向。 在生命科学领域，该项目将从算法的角度探索突变的真实本质问题，并将扩展最近的研究，旨在通过计算理解长期记忆以及语法和语言，该奖项反映了NSF的法定使命，并被认为是值得通过评估使用基金会的智力价值和更广泛的支持。影响审查标准。

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.