January 28, 2012

Understanding, Coping with, and Benefiting from Intractability


Project funded by the NSF expeditions program.


In an expedition to Understand, Cope with, and Benefit From Intractability, researchers from Princeton University, Rutgers University, New York University and the Institute for Advanced Study are attacking some of the deepest problems in computer science, as they strive to bridge fundamental gaps in the current theory of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits one's ability to understand nature and design systems. The PIs hope to chart new paths along the mysterious frontier between the tractable and the intractable.

Our effort has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines, including computational complexity, cryptography, analysis, geometry, combinatorics, quantum mechanics, and dynamical systems.

NSF logo IAS NYU Princeton University Rutgers University