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

Columbia University, New York NY

Investigators

Abstract

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.