Christos Papadimitriou and Mihalis Yannakakis receive $1.2M NSF grant

The National Science Foundation (NSF) has awarded a $1.2M, four-year grant to computer science theorists Christos Papadimitriou and Mihalis Yannakakis for their proposal “Research in Algorithms and Complexity: Total Functions, Games, and the Brain.”

The following is an abstract of the work to be done under the grant.

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? – that is to say, is exponential exhaustive search for a solution always avoidable?  Papadimitriou and Yannakakis have over the past four decades contributed much to this edifice of mathematical research in computer science, often in close collaboration; in addition, they have successfully applied the kind of incisive mindset known as “algorithmic thinking” to important problems in other sciences, such as economics and biology.

For this project, they will join efforts again 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. Papadimitriou and Yannakakis will train PhD and Masters students – and possibly undergraduates as well – on these research topics, and will disseminate the findings of this research 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.

In more detail, Papadimitriou and Yannakakis 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; they will investigate the complexity of an as yet unexplored, from this point of view, Tarski-like fixed point theorem widely used in economics; they will revisit the approximability of the traveling salesperson problem; and will explore a new kind of algorithmic notion of robustness based on dense nets of algorithms.  In algorithmic game theory, Papadimitriou and Yannakakis will 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; they will also research a new game theoretic solution concept based on the topology of dynamical systems; finally, they will pursue the proof of an intriguing new complexity-theoretic conjecture about the inaccessibility of Nash equilibria.  They will also continue their work in certain promising directions at the interface of game theory and learning theory.  In the life sciences, they will explore from the algorithmic point of view the problem of the true nature of mutations, and they will work on extending recent research with collaborators aiming at the computational understanding of how long-term memory, as well as syntax and language, are achieved in the human brain.

Posted 04/06/2018