Courant Institute Part of $10 Million NSF Grant to Address “Intractable” Mathematical Problems

By James Devitt

NYU’s Courant Institute of Mathematical Sciences and its institutional partners—Princeton and Rutgers universities and the Institute for Advanced Study—have received a $10 million grant from the National Science Foundation to bridge fundamental gaps in our understanding of the power and limits of efficient algorithms.
    Despite advances in computing power, many mathematical problems are so complex that they are considered “intractable.” Computational intractability, a concept that permeates science, mathematics, and engineering, limits our ability to understand nature or to design systems. With the NSF grant, the research team will seek to better understand the boundary between tractable and intractable computational endeavors.
    Their work, the NSF noted in announcing the grant, has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as secure cryptography, e-commerce, and quantum computing—an emerging field that aims to build computers by harnessing the physical properties of subatomic particles.
    The NYU re¬search¬ers participating on the multi-institutional team are Subhash Khot and Assaf Naor, both associate professors of computer science. NSF also provided $10 million grants to three other multi-institutional research teams.
    The team will also develop instructional materials for high school students and their teachers to advance mathematical education and prepare students to pursue advanced mathematical and computer science studies in universities. The grant is part of NSF’s “Expeditions in Computing” initiative, which funds teams of researchers and educators to pursue far-reaching research agendas that promise significant advances in the computing frontier and great benefit to society.


Courant’s Assaf Naor (above), associate professor of computer science, and Subhash Khot (inset), associate professor of computer science, are part of the multi-institutional research team