On this page, we highlight some high-impact research efforts at CCI. For year-by-year summaries of our activities, see the following reports:
For a list of research papers authored or coauthored by CCI members, please see:
Computational Intractability Applied to Understanding the Risks of Financial Derivatives
This is an area initiated by coPI Bernard Chazelle, whereby insights from theoretical computer science are used to explain properties of large systems of interacting agents (which have been long studied using continuous tools from dynamical systems).
The Unique Games Conjecture
Thus the problem is very evenly poised and we hope it will be soon resolved.
People involved in this research:
Approximately Hard: The Unique Games Conjecture. Erica Klarreich. Simons Foundation MPS Featured Article, Oct 2011.
Unique Games: A 3-act play. Richard Lipton’s article on his popular blog.
Approximation algorithms are efficient heuristics with provable guarantees for hard optimization problems. Modifying the problem so it can be solved by a mathematical program (a mathematical relaxation) and using the solution to solve the original problem is an especially powerful paradigm. We highlight two strands of research at the center (amongst several) in this area.