New York University’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. 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.

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 quantum computing and secure cryptography.

The NYU researchers who comprise the multi-institutional team are Subhash Khot, an associate professor of computer science, and Assaf Noar, an associate professor of mathematics. NSF also provided $10 million grants to three other multi-institutional research teams.

To read the NSF press release, go to: http://www.nsf.gov/news/newssumm.jsp?cntnid=112075&org=NSF&from=news