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
Women in Theory 2010 Workshop
Jun ’10Jun1923 Women In Theory 2010 June 19-23, 2010 at Princeton University Program chair: Tal Rabin. Local co-chairs: Boaz Barak and Moses Charikar. WomenInTheory2010 {at} gmail(.)com var mailNode = document.getElementById('emob-JbzraVaGurbel2010@tznvy.pbz-52'); ...
Read more of this articleNovember 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 article