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
November 6th Center Meeting
Nov610:00 am The Novermber 6 Center Meeting will be held in Room 402 of the Princeton Computer Science building. The schedule is given below: 10:00 – 10:45 Administrative meeting (Only for the Principal Investigators). 10:45...
Read more of this articleNew paper on complexity and financial derivatives
Sanjeev Arora, Boaz Barak, Markus Brunnermeier and Rong Ge just posted a paper on Computational Complexity and Information Asymmetry in Financial Products. (Link is to an informal “Frequently Asked Question” page,...
Read more of this articlePseudorandomness workshop at IAS June 14-18
Jun ’10Jun1418 IAS is co-organizing with the center for computational intractability a workshop on Pseudo-randomness in Mathematical Structures on June 14-18. Organizers: Jean Bourgain, Russell Impagliazzo, Peter...
Read more of this articleRegistration for Natural Algorithms Workshop
Please fill this form to register to the Natural Algorithms workshop on November 2-3, 2009. (Note: registration to the banquet on Nov 2nd is now closed) General Information Your Name(required) Email(valid...
Read more of this articleProgram for Barriers in Computational Complexity Workshop
Click here for the workshop’s homepage This is a tentative program and subject to change. Barriers in Computational Complexity workshop Click here for PDF version of program. Talks are in Room 101 in the Friend Center auditorium,...
Read more of this article