Discrete Models and Algorithms in the Sciences

The proposal contains four major computational themes, which are linked in various ways.

Quantum Computation: a study of novel quantum algorithms, of entanglement as a computational resource, and of connections to fundamental issues in quantum physics, such as the transition from classical to quantum.

Modeling the Regulatory Processes of the Cell: in the post-genomic era, the computational modeling of the operation of an entire cell at the level of interactions among genes, proteins and environmental conditions.

Statistical Physics and Computational Complexity: a study of central concepts of statistical physics, such as phase transitions and critical exponents, with emphasis on their computational manifestations and their relevance to the analysis of large systems with local interactions.

Mathematical Economics and the Internet: a study of the Internet as a novel computational artifact and a complex economic arena, as well as of the algorithmic adaptations of Game Theory and Mechanism Design necessary for such a study.

Each of the four PIs (Richard Karp, Christos Papadimitriou, Alistair Sinclair, and Umesh Vazirani) has a track record of research in at least one of the above areas, and a substantial interest in at least one other. The project also includes one senior scientist from each of the four areas: Birgitta Whaley (Quantum Physics), Adam Arkin (Quantitative Biology), Yuval Peres (Probability and Statistical Physics), and Scott Shenker (Economics and the Internet). The project recognizes that a computational perspective is becoming increasingly important in the Natural and Mathematical Sciences, and conversely that the Sciences are posing new challenges for the theory of computation. It aims to foster this connection within a dedicated program of research and graduate education.