ITR/SY: Discrete Models & Algorithms in the Sciences

点击翻译按钮获取中文摘要

The research is centered on four major computational themes which are linked in various ways:1. 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. 2. 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.3. 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.4. 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.The four PIs --- Richard Karp, Christos Papadimitriou, Alistair Sinclair and Umesh Vazirani --- are all based in the Computer Science Division at UC Berkeley. Each of them 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 research is rooted in a realization 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, many of which are related. It aims to foster this connection within a dedicated program of research and graduate education.