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 will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable.
This 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, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics.
Highlights
Subhash Khot wins Waterman award!
Center PI Subhash Khot won the extremely prestigious Waterman Award. The annual award recognizes an outstanding young researcher in any field of science or engineering supported by the National Science Foundation. In addition...
Read more of this articleFebruary 5 Center Meeting
Feb510:00 am The next center meeting will be on Friday Feb 5 at the usual place (room 405). The schedule appears below: 10:00 – 10:30 – PI only meeting 10:30 – 11:45 - “Algebraic complexity and the sum-of-squares problem”...
Read more of this articleNew TCS postdocs/jobs website
We’ve setup the page http://intractability.princeton.edu/jobs/ as a central location for advertising postdocs and other positions in theoretical computer science. Please visit the page to view open positions or notify us...
Read more of this articlePostdoc positions available
Postdoc positions are available in the center for computational intractability, deadline to apply and for reference letters is January 1, 2010. Click here for instructions how to apply. See also this site for postdoc opportunities...
Read more of this articleDecember 4 Center Meeting
The last meeting for the intractability center this calendar year will be held on December 4. We shall start the day in room 405, and then move to the small auditorium when it is available, for the two afternoon talks. In room...
Read more of this article